<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,user-scalable=no"><title>数据结构 | InsectMk的个人空间</title><meta name="keywords" content="数据结构"><meta name="author" content="InsectMk,3067836615@qq.com"><meta name="copyright" content="InsectMk"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#f7f9fe"><meta name="mobile-web-app-capable" content="yes"><meta name="apple-touch-fullscreen" content="yes"><meta name="apple-mobile-web-app-title" content="数据结构"><meta name="application-name" content="数据结构"><meta name="apple-mobile-web-app-capable" content="yes"><meta name="apple-mobile-web-app-status-bar-style" content="#f7f9fe"><meta property="og:type" content="article"><meta property="og:title" content="数据结构"><meta property="og:url" content="https://insectmk.top/posts/79666db/index.html"><meta property="og:site_name" content="InsectMk的个人空间"><meta property="og:description" content="数据结构引入对于程序员来说，数据结构是一门非常重要的科目，但是也是一门比较难以掌握的科目，这里记录了自己在大学课程中的一些实践代码，方便以后回来看看自己写的数据结构有多烂…… 线性表顺序结构线性表的顺序存储，C++代码实现如下 SeqlList.h，如果一个类使用了模板的话，不能将实现与定义拆分成两"><meta property="og:locale" content="zh-CN"><meta property="og:image" content="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/cover.jpg"><meta property="article:author" content="InsectMk"><meta property="article:tag" content="[&quot;InsectMk&quot;,&quot;个人博客&quot;]"><meta name="twitter:card" content="summary"><meta name="twitter:image" content="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/cover.jpg"><meta name="description" content="数据结构引入对于程序员来说，数据结构是一门非常重要的科目，但是也是一门比较难以掌握的科目，这里记录了自己在大学课程中的一些实践代码，方便以后回来看看自己写的数据结构有多烂…… 线性表顺序结构线性表的顺序存储，C++代码实现如下 SeqlList.h，如果一个类使用了模板的话，不能将实现与定义拆分成两"><link rel="shortcut icon" href="/static/img/website/favicon.jpg"><link rel="canonical" href="https://insectmk.top/posts/79666db/"><link rel="preconnect" href="//cdn.cbd.int"><link rel="preconnect" href="//busuanzi.ibruce.info"><meta name="google-site-verification" content="xxx"><meta name="baidu-site-verification" content="code-xxx"><meta name="msvalidate.01" content="xxx"><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.cbd.int/node-snackbar@0.1.16/dist/snackbar.min.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://cdn.cbd.int/@fancyapps/ui@5.0.28/dist/fancybox/fancybox.css" media="print" onload='this.media="all"'><script>let GLOBAL_CONFIG={linkPageTop:{enable:!0,title:"与数百名博主无限进步",addFriendPlaceholder:"昵称（请勿包含博客等字样）：\n网站地址（要求博客地址，请勿提交个人主页）：\n头像图片url（请提供尽可能清晰的图片，我会上传到我自己的图床）：\n描述：\n站点截图（可选）：\n"},peoplecanvas:{enable:!0,img:"https://image.insectmk.cn/hexo-gitee-blog/article/_post/summary/hello-world/cover.jpg"},postHeadAiDescription:void 0,diytitle:void 0,LA51:void 0,greetingBox:void 0,twikooEnvId:"",commentBarrageConfig:void 0,root:"/",preloader:{source:3},friends_vue_info:void 0,navMusic:!0,mainTone:void 0,authorStatus:void 0,algolia:void 0,localSearch:{path:"/search.xml",preload:!0,languages:{hits_empty:"找不到您查询的内容：${query}"}},translate:{defaultEncoding:2,translateDelay:0,msgToTraditionalChinese:"繁",msgToSimplifiedChinese:"简",rightMenuMsgToTraditionalChinese:"转为繁体",rightMenuMsgToSimplifiedChinese:"转为简体"},noticeOutdate:void 0,highlight:{plugin:"highlight.js",highlightCopy:!0,highlightLang:!0,highlightHeightLimit:330},copy:{success:"复制成功",error:"复制错误",noSupport:"浏览器不支持"},relativeDate:{homepage:!1,simplehomepage:!0,post:!1},runtime:"天",date_suffix:{just:"刚刚",min:"分钟前",hour:"小时前",day:"天前",month:"个月前"},copyright:{copy:!0,copyrightEbable:!1,limitCount:50,languages:{author:"作者: InsectMk",link:"链接: ",source:"来源: InsectMk的个人空间",info:"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。",copySuccess:"复制成功，复制和转载请标注本文地址"}},lightbox:"fancybox",Snackbar:{chs_to_cht:"你已切换为繁体",cht_to_chs:"你已切换为简体",day_to_night:"你已切换为深色模式",night_to_day:"你已切换为浅色模式",bgLight:"#425AEF",bgDark:"#1f1f1f",position:"top-center"},source:{justifiedGallery:{js:"https://cdn.cbd.int/flickr-justified-gallery@2.1.2/dist/fjGallery.min.js",css:"https://cdn.cbd.int/flickr-justified-gallery@2.1.2/dist/fjGallery.css"}},isPhotoFigcaption:!1,islazyload:!1,isAnchor:!1,shortcutKey:void 0,autoDarkmode:!0}</script><script id="config-diff">var GLOBAL_CONFIG_SITE={configTitle:"InsectMk的个人空间",title:"数据结构",postAI:"",pageFillDescription:"数据结构, 引入, 线性表, 顺序结构, 单链表, 顺序栈, 队列, 模式匹配, BF, KMP, 扩展数据结构引入对于程序员来说数据结构是一门非常重要的科目但是也是一门比较难以掌握的科目这里记录了自己在大学课程中的一些实践代码方便以后回来看看自己写的数据结构有多烂线性表顺序结构线性表的顺序存储代码实现如下如果一个类使用了模板的话不能将实现与定义拆分成两个文件这个问题我卡了很久很久设置顺序表最多能存储的元素的数量相当于的泛型在叫模板无参构造建立空的顺序表有参构造建立长度为的顺序表析构函数就是在对象销毁时会被执行获取线性表的长度按位查找查找第个元素按值查找查找值为的元素插入操作在第个位置插入值为的元素删除操作删除第个元素判断线性表是否为空遍历操作按序号依次输出各元素存放数据元素的数组线性表的长度无参构造建立空的顺序表有参构造建立长度为的顺序表参数非法析构函数就是在对象销毁时会被执行被销毁了获取线性表的长度按位查找查找第个元素位置不存在按值查找查找值为的元素没找到插入操作在第个位置插入值为的元素已满位置错误删除操作删除第个元素位置错误判断线性表是否为空遍历操作按序号依次输出各元素做了个菜单自我感觉良好菜单清除控制台未使用元素个最大容量个顺序表状态插入一个数字指定位置插入一个数字获取某个数的具体位置获取一个具体位置的数删除一个指定位置的数退出演示请输入对应服务编号出错啦错误消息菜单插入一个数字请输入要插入的数字指定位置插入一个数字请输入指定位置与要插入的数字获取某个数的具体位置请输入要查询的数所查数第一次出现的位置是没有查到哦获取一个具体位置的数请输入要查找的位置所在位置的数是删除一个指定位置的数请输入要删除的位置感谢体验再见输入有误清除屏幕未使用运行效果单链表单链表有头插法和尾插法的说法案例代码具体体现在链表的有参初始工作中定义单链表的结点相当于的泛型在叫模板无参构造建立空的顺序表有参构造建立长度为的顺序表析构函数就是在对象销毁时会被执行获取线性表的长度按位查找查找第个结点按值查找查找值为的结点插入操作在第个位置插入值为的结点删除操作删除第个结点判断线性表是否为空遍历操作按序号依次输出各结点单链表的头结点无参构造建立只有头节点的单链表有参构造建立长度为的顺序表头插法有参构造建立长度为的顺序表尾插法析构函数就是在对象销毁时会被执行被销毁了获取线性表的长度按位查找查找第个结点位置不存在按值查找查找值为的结点没找到插入操作在第个位置插入值为的结点位置错误删除操作删除第个结点位置错误判断线性表是否为空遍历操作按序号依次输出各结点菜单清除控制台未使用元素个单链表状态插入一个数字指定位置插入一个数字获取某个数的具体位置获取一个具体位置的数删除一个指定位置的数退出演示请输入对应服务编号出错啦错误消息菜单插入一个数字请输入要插入的数字指定位置插入一个数字请输入指定位置与要插入的数字获取某个数的具体位置请输入要查询的数所查数第一次出现的位置是没有查到哦获取一个具体位置的数请输入要查找的位置所在位置的数是删除一个指定位置的数请输入要删除的位置感谢体验再见输入有误清除屏幕未使用运行效果和顺序表差不多就不过多展示了顺序栈栈结构就是先入后出后入先出使用顺序栈实现四则运算判断运算符优先级根据二元运算符运算构造函数析构函数入栈操作出栈操作去栈顶元素判断栈是否为空存放栈元素的数组栈顶元素在数组中的下标构造函数初始化栈顶元素下标析构函数入栈栈溢出出栈取栈顶判断栈是否为空判断运算符优先级不支持的运算符根据二元运算符运算不支持的运算符定义所有支持的运算符与用户输入用于存储运算数用于存储运算符用于存储程序会产生的数字将结束符号压入栈中方便优先级比较请输入你的表达式每次输入运算数运算符你的输入判断左括号判断是否为运算符不是运算符则为数字转为数字并压入数字栈转为数字将数字压入数字栈中判断右括号判断运算符优先级如果新运算的优先级比栈中低则先弹栈进行运算将运算结果压入数字栈中将用户输入的运算符压入运算符栈中如果新运算的优先级比栈中高则直接压入运算符栈计算结果运行效果队列先入先出后入后出这里使用循环队列完成了一个门诊看病的案例设置循环队列的长度构造函数析构函数入队操作将元素入队出队操作取队头元素判空长度数据队头和队尾以及长度长度构造函数将头尾都指向最后一个位置长度为析构函数入队满出队空队取队头空队判空用于存储病人信息的结构体编号姓名处理菜单选项并返回进入门诊的人选项排队的病人当前正在门诊的病人返回处理后正在门诊的病人输入数字选择对应功能诊室空闲编号姓名正在门诊请编号姓名做好准备当前还有人正在排队录入病人呼叫病人退出系统请选择错误的操作处理菜单选项并返回进入门诊的人选项排队的病人当前正在门诊的病人返回处理后正在门诊的病人再见请输入编号及姓名无人等待不支持的选项运行截图模式匹配字符串特有的功能暴力算法获取子串在主串中第一次出现的起始位置不存在则返回主串子串返回子串在主串中第一次出现的下标从起标不存在则返回设置主串每次匹配的起始位置记录主串某次匹配的位置变动记录子串匹配的位置变动当主串下标不为空时说明主串还没匹配完当子串下标不为空时说明子串还没被匹配完过当上面两个条件同时满足才执行循环如果在某次匹配中子串能与主串匹配上就一直往下匹配直到主串到底或者子串到底主串到底说明已经没法匹配了子串到底说明找到了子串在主串中的位置如果某次匹配没有匹配上就说明主串的这个位置匹配不上匹配的主串起始位置就往下走一位并将记录主串某次匹配的位置更新为主串新的匹配起始位置记录子串匹配的位置初始化为子串的第一个字符位置当匹配完成后如果子串的下标匹配记录为则说明子串匹配成功了就返回最后这次匹配的主串起始位置方法返回从起标如果子串下标匹配记录不为说明是主串的下标匹配记录为表明主串已经匹配到最后一个字符了也没有匹配到子串就返回表示没有找到子串给两个字符指针分配内存方便存字符串输入请输入主串请输入子串子串第一次在主串中出现的下标是没有匹配到子串内存释放运行截图对我来说很烧脑我这里的实现有问题但是能力只能先这样了用于装载数组数组指针数组长度获取子串的数组子串的首地址返回数组通过算法获取子串在主串中第一次出现的下标从起标未找到返回主串子串子串在主串中第一次出现的下标从起标未找到返回创建字符串接收变量终端输入请输入主串请输入子串输出结果没有在主串中找到子串子串在主串中第一次出现的下标为释放内存获取子串的数组子串的首地址返回数组计算数组长度给数组分配空间循环对应子串的每个字符下标当前子串字符下标需要比对的前后缀的最长长度假想没有前后缀根据前后缀最大长度从最大前后缀一直比较到最小前后缀找到下次对比子串的起始指针比较前后缀依次比较前后缀如果没配对就表示本次循环的前后缀长度不是最长的如果为真则写入偏移量并结束找最大前后缀将最大前后缀长度赋值给数组并退出通过算法获取子串在主串中第一次出现的下标从起标未找到返回主串子串子串在主串中第一次出现的下标从起标未找到返回获取子串的数组分别为主串的比较下标记录与子串的比较下标记录当主串比较到完或者子串比较完就终止循环子串比较完说明找到了子串的下标主串比较完说明没有找到子串比较完说明找到了子串的下标返回子串第一次出现的下标由于主串下标在比较时会往后走所以返回时要减去子串的长度子串没有比较完说明没有在主串中找到子串返回运行截图扩展双向链表一个结点包含前驱与后继的结点指针循环链表单链表尾结点的后继结点指针指向头结点双向链表头结点的前驱结点指针指向尾结点尾结点的后继结点指针指向头结点",isPost:!0,isHome:!1,isHighlightShrink:!1,isToc:!0,postUpdate:"2023-04-06 23:17:24",postMainColor:""}</script><noscript><style type="text/css">#nav{opacity:1}.justified-gallery img{opacity:1}#post-meta time,#recent-posts time{display:inline!important}</style></noscript><script>(e=>{e.saveToLocal={set:(e,t,a)=>{var o;0!==a&&(o=Date.now(),localStorage.setItem(e,JSON.stringify({value:t,expiry:o+864e5*a})))},get:e=>{var t=localStorage.getItem(e);if(t){t=JSON.parse(t);if(!(Date.now()>t.expiry))return t.value;localStorage.removeItem(e)}}},e.getScript=(o,c={})=>new Promise((t,e)=>{let a=document.createElement("script");a.src=o,a.async=!0,a.onerror=e,a.onload=a.onreadystatechange=function(){var e=this.readyState;e&&"loaded"!==e&&"complete"!==e||(a.onload=a.onreadystatechange=null,t())},Object.keys(c).forEach(e=>{a.setAttribute(e,c[e])}),document.head.appendChild(a)}),e.getCSS=(o,c=!1)=>new Promise((t,e)=>{let a=document.createElement("link");a.rel="stylesheet",a.href=o,c&&(a.id=c),a.onerror=e,a.onload=a.onreadystatechange=function(){var e=this.readyState;e&&"loaded"!==e&&"complete"!==e||(a.onload=a.onreadystatechange=null,t())},document.head.appendChild(a)}),e.activateDarkMode=()=>{document.documentElement.setAttribute("data-theme","dark"),null!==document.querySelector('meta[name="theme-color"]')&&document.querySelector('meta[name="theme-color"]').setAttribute("content","#18171d")},e.activateLightMode=()=>{document.documentElement.setAttribute("data-theme","light"),null!==document.querySelector('meta[name="theme-color"]')&&document.querySelector('meta[name="theme-color"]').setAttribute("content","#f7f9fe")};var e=saveToLocal.get("theme"),t=window.matchMedia("(prefers-color-scheme: dark)").matches,a=window.matchMedia("(prefers-color-scheme: light)").matches,o=window.matchMedia("(prefers-color-scheme: no-preference)").matches,c=!t&&!a&&!o,t=(void 0===e?(a?activateLightMode():t?activateDarkMode():(o||c)&&((a=(new Date).getHours())<=6||18<=a?activateDarkMode:activateLightMode)(),window.matchMedia("(prefers-color-scheme: dark)").addListener(e=>{void 0===saveToLocal.get("theme")&&(e.matches?activateDarkMode:activateLightMode)()})):("light"===e?activateLightMode:activateDarkMode)(),saveToLocal.get("aside-status"));void 0!==t&&("hide"===t?document.documentElement.classList.add("hide-aside"):document.documentElement.classList.remove("hide-aside"));/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)&&document.documentElement.classList.add("apple")})(window)</script><meta name="generator" content="Hexo 7.3.0"><link rel="alternate" href="/atom.xml" title="InsectMk的个人空间" type="application/atom+xml"><link rel="alternate" href="/rss2.xml" title="InsectMk的个人空间" type="application/rss+xml"></head><body data-type="anzhiyu"><div id="web_bg"></div><div id="an_music_bg"></div><div id="loading-box" onclick="document.getElementById(&quot;loading-box&quot;).classList.add(&quot;loaded&quot;)"><div class="loading-bg"><img class="loading-img nolazyload" alt="加载头像" src="/static/img/head/insectmk.jpg"><div class="loading-image-dot"></div></div></div><script>let preloader={endLoading:()=>{document.getElementById("loading-box").classList.add("loaded")},initLoading:()=>{document.getElementById("loading-box").classList.remove("loaded")}};window.addEventListener("load",()=>{preloader.endLoading()}),setTimeout(function(){preloader.endLoading()},1e4),document.addEventListener("pjax:send",()=>{preloader.initLoading()}),document.addEventListener("pjax:complete",()=>{preloader.endLoading()})</script><link rel="stylesheet" href="https://cdn.cbd.int/anzhiyu-theme-static@1.1.10/progress_bar/progress_bar.css"><script async src="https://cdn.cbd.int/pace-js@1.2.4/pace.min.js" data-pace-options="{ &quot;restartOnRequestAfter&quot;:false,&quot;eventLag&quot;:false}"></script><div class="post" id="body-wrap"><header class="not-top-img" id="page-header"><nav id="nav"><div id="nav-group"><span id="blog_name"><div class="back-home-button"><i class="anzhiyufont anzhiyu-icon-grip-vertical"></i><div class="back-menu-list-groups"><div class="back-menu-list-group"><div class="back-menu-list-title">网页</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://insectmk.cn/" title="主博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="主博客"><span class="back-menu-item-text">主博客</span></a><a class="back-menu-item" href="https://insectmk.top/" title="次博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="次博客"><span class="back-menu-item-text">次博客</span></a></div></div><div class="back-menu-list-group"><div class="back-menu-list-title">项目</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://gitee.com/insectmk/chatbot-web" title="智能聊天机器人网站"><img class="back-menu-item-icon" src="https://image.insectmk.cn/hexo-gitee-blog/project/icon/chatbot-web.jpg" alt="智能聊天机器人网站"><span class="back-menu-item-text">智能聊天机器人网站</span></a></div></div></div></div><a id="site-name" href="/" accesskey="h"><div class="title">InsectMk的个人空间</div><i class="anzhiyufont anzhiyu-icon-house-chimney"></i></a></span><div class="mask-name-container"><div id="name-container"><a id="page-name" href="javascript:anzhiyu.scrollToDest(0, 500)">PAGE_NAME</a></div></div><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-home"></use></svg><span>主页</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-hand-peace"></use></svg><span>娱乐</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/entertainment/gallery/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-images"></use></svg><span>图库</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-comments"></use></svg><span>交流</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/contact/comments/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-paper-plane"></use></svg><span>留言板</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/contact/link/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-link"></use></svg><span>友链</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-compass"></use></svg><span>目录</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/categories/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-archive"></use></svg><span>分类</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/tags/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-tags"></use></svg><span>标签</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/archives/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-folder-open"></use></svg><span>归档</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-server"></use></svg><span>服务</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/server/left4dead2/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-icons-left__dead_"></use></svg><span>求生之路</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/server/minecraft/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-minecraft"></use></svg><span>我的世界</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-clipboard"></use></svg><span>日志</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/log/website/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-website-with-different-sections"></use></svg><span>个人网站</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/log/pc/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-desktop"></use></svg><span>个人电脑</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-bars"></use></svg><span>其他</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/extend/remind/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-note"></use></svg><span>备忘</span></a></li></ul></div><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/about/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-id-card"></use></svg><span>关于</span></a></div></div></div><div id="nav-right"><div class="nav-button" id="randomPost_button"><a class="site-page" onclick="toRandomPost()" title="随机前往一个文章" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-dice"></i></a></div><div class="nav-button" id="search-button"><a class="site-page social-icon search" href="javascript:void(0);" title="搜索🔍" accesskey="s"><i class="anzhiyufont anzhiyu-icon-magnifying-glass"></i><span> 搜索</span></a></div><input id="center-console" type="checkbox"><label class="widget" for="center-console" title="中控台" onclick="anzhiyu.switchConsole()"><i class="left"></i><i class="widget center"></i><i class="widget right"></i></label><div id="console"><div class="console-card-group-reward"><ul class="reward-all console-card"><li class="reward-item"><a href="/static/img/website/reward/wechat.png" target="_blank"><img class="post-qr-code-img" alt="微信" src="/static/img/website/reward/wechat.png"></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="/static/img/website/reward/alipay.png" target="_blank"><img class="post-qr-code-img" alt="支付宝" src="/static/img/website/reward/alipay.png"></a><div class="post-qr-code-desc">支付宝</div></li></ul></div><div class="console-card-group"><div class="console-card-group-left"><div class="console-card" id="card-newest-comments"><div class="card-content"><div class="author-content-item-tips">互动</div><span class="author-content-item-title">最新评论</span></div><div class="aside-list"><span>正在加载中...</span></div></div></div><div class="console-card-group-right"><div class="console-card tags"><div class="card-content"><div class="author-content-item-tips">兴趣点</div><span class="author-content-item-title">寻找你感兴趣的领域</span><div class="card-tags"><div class="item-headline"></div><div class="card-tag-cloud"><a href="/tags/AOP/" style="font-size:1.05rem">AOP<sup>1</sup></a><a href="/tags/Butterfly/" style="font-size:1.05rem">Butterfly<sup>4</sup></a><a href="/tags/Docker/" style="font-size:1.05rem">Docker<sup>6</sup></a><a href="/tags/ElementUI/" style="font-size:1.05rem">ElementUI<sup>1</sup></a><a href="/tags/Frp/" style="font-size:1.05rem">Frp<sup>1</sup></a><a href="/tags/Hexo/" style="font-size:1.05rem">Hexo<sup>8</sup></a><a href="/tags/IntelliJ-IDEA/" style="font-size:1.05rem">IntelliJ IDEA<sup>1</sup></a><a href="/tags/JDK/" style="font-size:1.05rem">JDK<sup>1</sup></a><a href="/tags/JWT/" style="font-size:1.05rem">JWT<sup>1</sup></a><a href="/tags/Java/" style="font-size:1.05rem">Java<sup>35</sup></a><a href="/tags/Junit/" style="font-size:1.05rem">Junit<sup>1</sup></a><a href="/tags/Leanote/" style="font-size:1.05rem">Leanote<sup>1</sup></a><a href="/tags/Maven/" style="font-size:1.05rem">Maven<sup>2</sup></a><a href="/tags/MyBatisPlus/" style="font-size:1.05rem">MyBatisPlus<sup>1</sup></a><a href="/tags/MySQL5-7/" style="font-size:1.05rem">MySQL5.7<sup>1</sup></a><a href="/tags/Mybatis/" style="font-size:1.05rem">Mybatis<sup>1</sup></a><a href="/tags/MybatisPlus/" style="font-size:1.05rem">MybatisPlus<sup>1</sup></a><a href="/tags/OSS/" style="font-size:1.05rem">OSS<sup>1</sup></a><a href="/tags/Spring/" style="font-size:1.05rem">Spring<sup>2</sup></a><a href="/tags/Spring-Boot/" style="font-size:1.05rem">SpringBoot<sup>6</sup></a><a href="/tags/Vue2/" style="font-size:1.05rem">Vue2<sup>9</sup></a><a href="/tags/Vue3/" style="font-size:1.05rem">Vue3<sup>1</sup></a><a href="/tags/Vuetify/" style="font-size:1.05rem">Vuetify<sup>1</sup></a><a href="/tags/Vuex/" style="font-size:1.05rem">Vuex<sup>1</sup></a><a href="/tags/Waline/" style="font-size:1.05rem">Waline<sup>3</sup></a><a href="/tags/mvc/" style="font-size:1.05rem">mvc<sup>3</sup></a><a href="/tags/mybatis/" style="font-size:1.05rem">mybatis<sup>1</sup></a><a href="/tags/profile/" style="font-size:1.05rem">profile<sup>1</sup></a><a href="/tags/spring/" style="font-size:1.05rem">spring<sup>5</sup></a><a href="/tags/springboot/" style="font-size:1.05rem">springboot<sup>4</sup></a><a href="/tags/transaction/" style="font-size:1.05rem">transaction<sup>1</sup></a><a href="/tags/yaml/" style="font-size:1.05rem">yaml<sup>2</sup></a><a href="/tags/%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/" style="font-size:1.05rem">个人博客<sup>11</sup></a><a href="/tags/%E4%BA%8B%E5%8A%A1/" style="font-size:1.05rem">事务<sup>1</sup></a><a href="/tags/%E5%88%86%E9%A1%B5/" style="font-size:1.05rem">分页<sup>1</sup></a><a href="/tags/%E5%89%8D%E7%AB%AF/" style="font-size:1.05rem">前端<sup>1</sup></a><a href="/tags/%E6%9C%8D%E5%8A%A1%E5%99%A8/" style="font-size:1.05rem">服务器<sup>20</sup></a><a href="/tags/%E6%AF%95%E4%B8%9A%E8%AE%BE%E8%AE%A1/" style="font-size:1.05rem">毕业设计<sup>14</sup></a><a href="/tags/%E7%A6%85%E9%81%93/" style="font-size:1.05rem">禅道<sup>1</sup></a><a href="/tags/%E7%BB%BF%E8%89%B2%E8%A7%A3%E5%8E%8B/" style="font-size:1.05rem">绿色解压<sup>1</sup></a></div></div><hr></div></div><div class="console-card history"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-box-archiv"></i><span>文章</span></div><div class="card-archives"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-archive"></i><span>归档</span><a class="card-more-btn" href="/archives/" title="查看更多"> <i class="anzhiyufont anzhiyu-icon-angle-right"></i></a></div><ul class="card-archive-list"><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/07/"><span class="card-archive-list-date">七月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">4</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/06/"><span class="card-archive-list-date">六月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">1</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/05/"><span class="card-archive-list-date">五月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">4</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/04/"><span class="card-archive-list-date">四月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">8</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/03/"><span class="card-archive-list-date">三月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">9</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/02/"><span class="card-archive-list-date">二月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">5</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/01/"><span class="card-archive-list-date">一月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">5</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2023/10/"><span class="card-archive-list-date">十月 2023</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">8</span><span>篇</span></div></a></li></ul></div><hr></div></div></div><div class="button-group"><div class="console-btn-item"><a class="darkmode_switchbutton" title="显示模式切换" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-moon"></i></a></div><div class="console-btn-item" id="consoleHideAside" onclick="anzhiyu.hideAsideBtn()" title="边栏显示控制"><a class="asideSwitch"><i class="anzhiyufont anzhiyu-icon-arrows-left-right"></i></a></div><div class="console-btn-item" id="consoleMusic" onclick="anzhiyu.musicToggle()" title="音乐开关"><a class="music-switch"><i class="anzhiyufont anzhiyu-icon-music"></i></a></div></div><div class="console-mask" onclick="anzhiyu.hideConsole()" href="javascript:void(0);"></div></div><div class="nav-button" id="nav-totop"><a class="totopbtn" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-arrow-up"></i><span id="percent" onclick="anzhiyu.scrollToDest(0,500)">0</span></a></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);" title="切换"><i class="anzhiyufont anzhiyu-icon-bars"></i></a></div></div></div></nav></header><main id="blog-container"><div class="layout" id="content-inner"><div id="post"><div id="post-info"><div id="post-firstinfo"><div class="meta-firstline"><a class="post-meta-original">原创</a><span class="post-meta-categories"><span class="post-meta-separator"></span><i class="anzhiyufont anzhiyu-icon-inbox post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E7%9F%A5%E8%AF%86/" itemprop="url">知识</a></span><span class="article-meta tags"><a class="article-meta__tags" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" tabindex="-1" itemprop="url"> <span><i class="anzhiyufont anzhiyu-icon-hashtag"></i>数据结构</span></a></span></div></div><h1 class="post-title" itemprop="name headline">数据结构</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="anzhiyufont anzhiyu-icon-calendar-days post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" itemprop="dateCreated datePublished" datetime="2023-03-17T15:17:24.000Z" title="发表于 2023-03-17 23:17:24">2023-03-17</time><span class="post-meta-separator"></span><i class="anzhiyufont anzhiyu-icon-history post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" itemprop="dateCreated datePublished" datetime="2023-04-06T15:17:24.000Z" title="更新于 2023-04-06 23:17:24">2023-04-06</time></span></div><div class="meta-secondline"><span class="post-meta-separator"></span><span class="post-meta-wordcount"><i class="anzhiyufont anzhiyu-icon-file-word post-meta-icon" title="文章字数"></i><span class="post-meta-label" title="文章字数">字数总计:</span><span class="word-count" title="文章字数">6.4k</span><span class="post-meta-separator"></span><i class="anzhiyufont anzhiyu-icon-clock post-meta-icon" title="阅读时长"></i><span class="post-meta-label" title="阅读时长">阅读时长:</span><span>29分钟</span></span><span class="post-meta-separator"></span><span data-flag-title="数据结构"><i class="anzhiyufont anzhiyu-icon-fw-eye post-meta-icon"></i><span class="post-meta-label" title="阅读量">阅读量:</span><span class="waline-pageview-count" data-path="/posts/79666db/" title="访问量"><i class="anzhiyufont anzhiyu-icon-spinner anzhiyu-spin"></i></span></span><span class="post-meta-separator"> </span><span class="post-meta-position" title="作者IP属地为成都"><i class="anzhiyufont anzhiyu-icon-location-dot"></i>成都</span><span class="post-meta-separator"></span><span class="post-meta-commentcount"><i class="anzhiyufont anzhiyu-icon-comments post-meta-icon"></i><span class="post-meta-label">评论数:</span><a href="/posts/79666db/#post-comment"><span class="waline-comment-count" data-path="/posts/79666db/"><i class="anzhiyufont anzhiyu-icon-spinner anzhiyu-spin"></i></span></a></span></div></div></div><article class="post-content" id="article-container" itemscope itemtype="https://insectmk.top/posts/79666db/"><header><a class="post-meta-categories" href="/categories/%E7%9F%A5%E8%AF%86/" itemprop="url">知识</a><a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" tabindex="-1" itemprop="url">数据结构</a><h1 id="CrawlerTitle" itemprop="name headline">数据结构</h1><span itemprop="author" itemscope itemtype="http://schema.org/Person">InsectMk</span><time itemprop="dateCreated datePublished" datetime="2023-03-17T15:17:24.000Z" title="发表于 2023-03-17 23:17:24">2023-03-17</time><time itemprop="dateCreated datePublished" datetime="2023-04-06T15:17:24.000Z" title="更新于 2023-04-06 23:17:24">2023-04-06</time></header><h1 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h1><h2 id="引入"><a href="#引入" class="headerlink" title="引入"></a>引入</h2><p>对于程序员来说，数据结构是一门非常重要的科目，但是也是一门比较难以掌握的科目，这里记录了自己在大学课程中的一些实践代码，方便以后回来看看自己写的数据结构有多烂……</p><h2 id="线性表"><a href="#线性表" class="headerlink" title="线性表"></a>线性表</h2><h3 id="顺序结构"><a href="#顺序结构" class="headerlink" title="顺序结构"></a>顺序结构</h3><p>线性表的顺序存储，C++代码实现如下</p><p><strong>SeqlList.h</strong>，如果一个类使用了模板的话，不能将实现与定义拆分成两个文件，这个问题我卡了很久很久~</p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">pragma</span> once</span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> MaxSize = <span class="number">200</span>;			<span class="comment">// 设置顺序表最多能存储的元素的数量</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType = <span class="type">int</span>&gt;	<span class="comment">// 相当于Java的泛型，在C++叫模板</span></span><br><span class="line"><span class="keyword">class</span> SeqList</span><br><span class="line">&#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="built_in">SeqList</span>();						<span class="comment">// 无参构造，建立空的顺序表</span></span><br><span class="line">	<span class="built_in">SeqList</span>(DataType a[], <span class="type">int</span> n);	<span class="comment">// 有参构造，建立长度为n的顺序表</span></span><br><span class="line">	~<span class="built_in">SeqList</span>();						<span class="comment">// 析构函数，就是在对象销毁时会被执行</span></span><br><span class="line">	<span class="function"><span class="type">int</span> <span class="title">Length</span><span class="params">()</span></span>;					<span class="comment">// 获取线性表的长度</span></span><br><span class="line">	<span class="function">DataType <span class="title">Get</span><span class="params">(<span class="type">int</span> i)</span></span>;			<span class="comment">// 按位查找，查找第i个元素</span></span><br><span class="line">	<span class="function"><span class="type">int</span> <span class="title">Locate</span><span class="params">(DataType x)</span></span>;			<span class="comment">// 按值查找，查找值为x的元素</span></span><br><span class="line">	<span class="function"><span class="type">void</span> <span class="title">Insert</span><span class="params">(<span class="type">int</span> i, DataType x)</span></span>;	<span class="comment">// 插入操作，在第i个位置插入值为x的元素</span></span><br><span class="line">	<span class="function">DataType <span class="title">Delete</span><span class="params">(<span class="type">int</span> i)</span></span>;			<span class="comment">// 删除操作，删除第i个元素</span></span><br><span class="line">	<span class="function"><span class="type">int</span> <span class="title">Empty</span><span class="params">()</span></span>;					<span class="comment">// 判断线性表是否为空</span></span><br><span class="line">	<span class="function"><span class="type">void</span> <span class="title">PrintList</span><span class="params">()</span></span>;				<span class="comment">// 遍历操作，按序号依次输出各元素</span></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">	DataType data[MaxSize];			<span class="comment">// 存放数据元素的数组</span></span><br><span class="line">	<span class="type">int</span> length;						<span class="comment">// 线性表的长度</span></span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 无参构造，建立空的顺序表</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">SeqList&lt;DataType&gt;::<span class="built_in">SeqList</span>() &#123;</span><br><span class="line">	<span class="keyword">this</span>-&gt;length = <span class="number">0</span>;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 有参构造，建立长度为n的顺序表</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">SeqList&lt;DataType&gt;::<span class="built_in">SeqList</span>(DataType a[], <span class="type">int</span> n) &#123;</span><br><span class="line">	<span class="keyword">if</span> (n &gt; MaxSize) <span class="keyword">throw</span> <span class="string">&quot;参数非法&quot;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">		<span class="keyword">this</span>-&gt;data[i] = a[i];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">this</span>-&gt;length = n;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 析构函数，就是在对象销毁时会被执行</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">SeqList&lt;DataType&gt;::~<span class="built_in">SeqList</span>() &#123;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;被销毁了&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 获取线性表的长度</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">int</span> SeqList&lt;DataType&gt;::<span class="built_in">Length</span>() &#123;</span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">this</span>-&gt;length;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 按位查找，查找第i个元素</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">DataType SeqList&lt;DataType&gt;::<span class="built_in">Get</span>(<span class="type">int</span> i) &#123;</span><br><span class="line">	<span class="keyword">if</span> (i &lt; <span class="number">1</span> || i &gt; <span class="keyword">this</span>-&gt;length) &#123;</span><br><span class="line">		<span class="keyword">throw</span> <span class="string">&quot;位置不存在&quot;</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">this</span>-&gt;data[i - <span class="number">1</span>];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 按值查找，查找值为x的元素</span></span><br><span class="line"><span class="comment">// 0：没找到</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">int</span> SeqList&lt;DataType&gt;::<span class="built_in">Locate</span>(DataType x) &#123;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; length; i++) &#123;</span><br><span class="line">		<span class="keyword">if</span> (<span class="keyword">this</span>-&gt;data[i] == x) &#123;</span><br><span class="line">			<span class="keyword">return</span> i + <span class="number">1</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 插入操作，在第i个位置插入值为x的元素</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">void</span> SeqList&lt;DataType&gt;::<span class="built_in">Insert</span>(<span class="type">int</span> i, DataType x) &#123;</span><br><span class="line">	<span class="keyword">if</span> (length &gt;= MaxSize) <span class="keyword">throw</span> <span class="string">&quot;已满&quot;</span>;</span><br><span class="line">	<span class="keyword">if</span> (i &lt; <span class="number">1</span> || i &gt; length + <span class="number">1</span>) <span class="keyword">throw</span> <span class="string">&quot;位置错误&quot;</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> j = length; j &gt;= i - <span class="number">1</span>; j--) &#123;</span><br><span class="line">		<span class="keyword">this</span>-&gt;data[j + <span class="number">1</span>] = <span class="keyword">this</span>-&gt;data[j];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">this</span>-&gt;data[i - <span class="number">1</span>] = x;</span><br><span class="line">	<span class="keyword">this</span>-&gt;length++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 删除操作，删除第i个元素</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">DataType SeqList&lt;DataType&gt;::<span class="built_in">Delete</span>(<span class="type">int</span> i) &#123;</span><br><span class="line">	<span class="keyword">if</span> (i &lt; <span class="number">1</span> || i &gt; length) <span class="keyword">throw</span> <span class="string">&quot;位置错误&quot;</span>;</span><br><span class="line"></span><br><span class="line">	DataType del = <span class="keyword">this</span>-&gt;<span class="built_in">Get</span>(i);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> j = i<span class="number">-1</span>; j &lt; length - <span class="number">1</span>; j++) &#123;</span><br><span class="line">		<span class="keyword">this</span>-&gt;data[j] = <span class="keyword">this</span>-&gt;data[j + <span class="number">1</span>];</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">this</span>-&gt;length--;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> del;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 判断线性表是否为空</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">int</span> SeqList&lt;DataType&gt;::<span class="built_in">Empty</span>() &#123;</span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">this</span>-&gt;length ? <span class="number">0</span> : <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 遍历操作，按序号依次输出各元素</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">void</span> SeqList&lt;DataType&gt;::<span class="built_in">PrintList</span>() &#123;</span><br><span class="line">	<span class="keyword">if</span> (<span class="keyword">this</span>-&gt;<span class="built_in">Empty</span>()) &#123;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;&#123;&#125;&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="type">int</span> i = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;&#123;&quot;</span>;</span><br><span class="line">	<span class="keyword">for</span> (; i &lt; length - <span class="number">1</span>; i++) &#123;</span><br><span class="line">		cout &lt;&lt; <span class="keyword">this</span>-&gt;data[i] &lt;&lt; <span class="string">&quot;,&quot;</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt; <span class="keyword">this</span>-&gt;data[i] &lt;&lt; <span class="string">&quot;&#125;&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><p><strong>Main.cpp</strong>，做了个菜单，自我感觉良好</p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&quot;SeqList.h&quot;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 菜单</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType = <span class="type">int</span>&gt;</span><br><span class="line"><span class="type">void</span> <span class="built_in">Menu</span>(<span class="type">int</span> choose, SeqList&lt;&gt;* list);</span><br><span class="line"><span class="comment">// 清除控制台（未使用）</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Clear</span><span class="params">()</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	SeqList&lt;&gt; list;</span><br><span class="line">	<span class="type">int</span> choose = <span class="number">-1</span>;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">while</span> (choose) &#123;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;--------------------------------&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;元素[&quot;</span> &lt;&lt; list.<span class="built_in">Length</span>() &lt;&lt; <span class="string">&quot;]个|最大容量[&quot;</span> &lt;&lt; MaxSize &lt;&lt; <span class="string">&quot;]个|顺序表状态&quot;</span>;</span><br><span class="line">		list.<span class="built_in">PrintList</span>();</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;1、插入一个数字&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;2、指定位置插入一个数字&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;3、获取某个数的具体位置&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;4、获取一个具体位置的数&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;5、删除一个指定位置的数&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;0、退出演示&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入对应服务编号：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; choose;</span><br><span class="line">		<span class="keyword">try</span> &#123;</span><br><span class="line">			<span class="built_in">Menu</span>(choose, &amp;list);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">catch</span> (<span class="type">const</span> <span class="type">char</span> * e) &#123;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;出错啦，错误消息：&quot;</span> &lt;&lt; e &lt;&lt; endl;</span><br><span class="line">		&#125;</span><br><span class="line">		cout &lt;&lt; endl &lt;&lt; <span class="string">&quot;--------------------------------&quot;</span> &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 菜单</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType = <span class="type">int</span>&gt;</span><br><span class="line"><span class="type">void</span> <span class="built_in">Menu</span>(<span class="type">int</span> choose, SeqList&lt;&gt;* list) &#123;</span><br><span class="line">	<span class="type">int</span> in_1 = <span class="number">0</span>, in_2 = <span class="number">0</span>, temp_1 = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">switch</span> (choose) &#123;</span><br><span class="line">		<span class="comment">// 插入一个数字</span></span><br><span class="line">	<span class="keyword">case</span> <span class="number">1</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入要插入的数字：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; in_1;</span><br><span class="line">		list-&gt;<span class="built_in">Insert</span>(list-&gt;<span class="built_in">Length</span>() + <span class="number">1</span>, in_1);</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">		<span class="comment">// 指定位置插入一个数字</span></span><br><span class="line">	<span class="keyword">case</span> <span class="number">2</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入指定位置与要插入的数字：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; in_1 &gt;&gt; in_2;</span><br><span class="line">		list-&gt;<span class="built_in">Insert</span>(in_1, in_2);</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">		<span class="comment">// 获取某个数的具体位置</span></span><br><span class="line">	<span class="keyword">case</span> <span class="number">3</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入要查询的数：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; in_1;</span><br><span class="line">		temp_1 = list-&gt;<span class="built_in">Locate</span>(in_1);</span><br><span class="line">		<span class="keyword">if</span> (temp_1) &#123;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;所查数第一次出现的位置是：&quot;</span> &lt;&lt; temp_1 &lt;&lt; endl;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;没有查到哦~&quot;</span> &lt;&lt; endl;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">		<span class="comment">// 获取一个具体位置的数</span></span><br><span class="line">	<span class="keyword">case</span> <span class="number">4</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入要查找的位置：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; in_1;</span><br><span class="line">		temp_1 = list-&gt;<span class="built_in">Get</span>(in_1);</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;所在位置的数是：&quot;</span> &lt;&lt; temp_1 &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">		<span class="comment">// 删除一个指定位置的数</span></span><br><span class="line">	<span class="keyword">case</span> <span class="number">5</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入要删除的位置：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; in_1;</span><br><span class="line">		list-&gt;<span class="built_in">Delete</span>(in_1);</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">	<span class="keyword">case</span> <span class="number">0</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;感谢体验，再见~&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">	<span class="keyword">default</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;输入有误&quot;</span> &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 清除屏幕（未使用）</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Clear</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;\x1B[2J\x1B[H&quot;</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><p><strong>运行效果</strong></p><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/image-20230317232746299.png" alt="image-20230317232746299"></p><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/image-20230317232856469.png" alt="image-20230317232856469"></p><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/image-20230317232916272.png" alt="image-20230317232916272"></p><h3 id="单链表"><a href="#单链表" class="headerlink" title="单链表"></a>单链表</h3><p>单链表有头插法和尾插法的说法，案例代码具体体现在链表的有参初始工作中</p><p><strong>LinkList.h</strong></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">pragma</span> once</span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 定义单链表的结点</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType = <span class="type">int</span>&gt;</span><br><span class="line"><span class="keyword">struct</span> Node &#123;</span><br><span class="line">	DataType data;</span><br><span class="line">	Node&lt;DataType&gt;* next;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType = <span class="type">int</span>&gt;	<span class="comment">// 相当于Java的泛型，在C++叫模板</span></span><br><span class="line"><span class="keyword">class</span> LinkList</span><br><span class="line">&#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="built_in">LinkList</span>();						<span class="comment">// 无参构造，建立空的顺序表</span></span><br><span class="line">	<span class="built_in">LinkList</span>(DataType a[], <span class="type">int</span> n);	<span class="comment">// 有参构造，建立长度为n的顺序表</span></span><br><span class="line">	~<span class="built_in">LinkList</span>();						<span class="comment">// 析构函数，就是在对象销毁时会被执行</span></span><br><span class="line">	<span class="function"><span class="type">int</span> <span class="title">Length</span><span class="params">()</span></span>;					<span class="comment">// 获取线性表的长度</span></span><br><span class="line">	<span class="function">DataType <span class="title">Get</span><span class="params">(<span class="type">int</span> i)</span></span>;			<span class="comment">// 按位查找，查找第i个结点</span></span><br><span class="line">	<span class="function"><span class="type">int</span> <span class="title">Locate</span><span class="params">(DataType x)</span></span>;			<span class="comment">// 按值查找，查找值为x的结点</span></span><br><span class="line">	<span class="function"><span class="type">void</span> <span class="title">Insert</span><span class="params">(<span class="type">int</span> i, DataType x)</span></span>;	<span class="comment">// 插入操作，在第i个位置插入值为x的结点</span></span><br><span class="line">	<span class="function">DataType <span class="title">Delete</span><span class="params">(<span class="type">int</span> i)</span></span>;			<span class="comment">// 删除操作，删除第i个结点</span></span><br><span class="line">	<span class="function"><span class="type">int</span> <span class="title">Empty</span><span class="params">()</span></span>;					<span class="comment">// 判断线性表是否为空</span></span><br><span class="line">	<span class="function"><span class="type">void</span> <span class="title">PrintList</span><span class="params">()</span></span>;				<span class="comment">// 遍历操作，按序号依次输出各结点</span></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">	Node&lt;DataType&gt;* header;			<span class="comment">// 单链表的头结点</span></span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 无参构造，建立只有头节点的单链表</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">LinkList&lt;DataType&gt;::<span class="built_in">LinkList</span>() &#123;</span><br><span class="line">	<span class="keyword">this</span>-&gt;header = <span class="keyword">new</span> Node&lt;DataType&gt;;</span><br><span class="line">	<span class="keyword">this</span>-&gt;header-&gt;next = <span class="literal">nullptr</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 有参构造，建立长度为n的顺序表，头插法</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">LinkList&lt;DataType&gt;::<span class="built_in">LinkList</span>(DataType a[], <span class="type">int</span> n) &#123;</span><br><span class="line">	<span class="keyword">this</span>-&gt;header = <span class="keyword">new</span> Node&lt;DataType&gt;;</span><br><span class="line">	<span class="keyword">this</span>-&gt;header-&gt;next = <span class="literal">nullptr</span>;</span><br><span class="line">	Node&lt;DataType&gt;* temp = <span class="literal">nullptr</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123;</span><br><span class="line">		temp = <span class="keyword">this</span>-&gt;header-&gt;next;</span><br><span class="line">		<span class="keyword">this</span>-&gt;header-&gt;next = <span class="keyword">new</span> Node&lt;DataType&gt;;</span><br><span class="line">		<span class="keyword">this</span>-&gt;header-&gt;next-&gt;data = a[i];</span><br><span class="line">		<span class="keyword">this</span>-&gt;header-&gt;next-&gt;next = temp;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//// 有参构造，建立长度为n的顺序表，尾插法</span></span><br><span class="line"><span class="comment">//template &lt;typename DataType&gt;</span></span><br><span class="line"><span class="comment">//LinkList&lt;DataType&gt;::LinkList(DataType a[], int n) &#123;</span></span><br><span class="line"><span class="comment">//	this-&gt;header = new Node&lt;DataType&gt;;</span></span><br><span class="line"><span class="comment">//	Node&lt;DataType&gt;* temp = this-&gt;header;</span></span><br><span class="line"><span class="comment">//	for (int i = 0; i &lt; n; i++) &#123;</span></span><br><span class="line"><span class="comment">//		temp-&gt;next = new Node&lt;DataType&gt;;</span></span><br><span class="line"><span class="comment">//		temp-&gt;next-&gt;data = a[i];</span></span><br><span class="line"><span class="comment">//		temp = temp-&gt;next;</span></span><br><span class="line"><span class="comment">//	&#125;</span></span><br><span class="line"><span class="comment">//	temp-&gt;next = nullptr;</span></span><br><span class="line"><span class="comment">//&#125;</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 析构函数，就是在对象销毁时会被执行</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">LinkList&lt;DataType&gt;::~<span class="built_in">LinkList</span>() &#123;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;被销毁了&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 获取线性表的长度</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">int</span> LinkList&lt;DataType&gt;::<span class="built_in">Length</span>() &#123;</span><br><span class="line">	<span class="type">int</span> cnt = <span class="number">0</span>;</span><br><span class="line">	Node&lt;DataType&gt;* temp = <span class="keyword">this</span>-&gt;header;</span><br><span class="line">	<span class="keyword">while</span> (temp-&gt;next != <span class="literal">nullptr</span>) &#123;</span><br><span class="line">		temp = temp-&gt;next;</span><br><span class="line">		cnt++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> cnt;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 按位查找，查找第i个结点</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">DataType LinkList&lt;DataType&gt;::<span class="built_in">Get</span>(<span class="type">int</span> i) &#123;</span><br><span class="line">	<span class="keyword">if</span> (i &lt; <span class="number">1</span> || i &gt; <span class="keyword">this</span>-&gt;<span class="built_in">Length</span>()) &#123;</span><br><span class="line">		<span class="keyword">throw</span> <span class="string">&quot;位置不存在&quot;</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	Node&lt;DataType&gt;* temp = <span class="keyword">this</span>-&gt;header;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; i; j++) &#123;</span><br><span class="line">		temp = temp-&gt;next;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> temp-&gt;data;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 按值查找，查找值为x的结点</span></span><br><span class="line"><span class="comment">// 0：没找到</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">int</span> LinkList&lt;DataType&gt;::<span class="built_in">Locate</span>(DataType x) &#123;</span><br><span class="line">	Node&lt;DataType&gt;* temp = header;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="keyword">this</span>-&gt;<span class="built_in">Length</span>(); i++) &#123;</span><br><span class="line">		temp = temp-&gt;next;</span><br><span class="line">		<span class="keyword">if</span> (temp-&gt;data == x) &#123;</span><br><span class="line">			<span class="keyword">return</span> i + <span class="number">1</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 插入操作，在第i个位置插入值为x的结点</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">void</span> LinkList&lt;DataType&gt;::<span class="built_in">Insert</span>(<span class="type">int</span> i, DataType x) &#123;</span><br><span class="line">	<span class="keyword">if</span> (i &lt; <span class="number">1</span> || i &gt; <span class="keyword">this</span>-&gt;<span class="built_in">Length</span>() + <span class="number">1</span>) <span class="keyword">throw</span> <span class="string">&quot;位置错误&quot;</span>;</span><br><span class="line"></span><br><span class="line">	Node&lt;DataType&gt;* temp = header, *new_node = <span class="keyword">new</span> Node&lt;DataType&gt;;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; i - <span class="number">1</span>; j++) &#123;</span><br><span class="line">		temp = temp-&gt;next;</span><br><span class="line">	&#125;</span><br><span class="line">	new_node-&gt;data = x;</span><br><span class="line">	new_node-&gt;next = temp-&gt;next;</span><br><span class="line">	temp-&gt;next = new_node;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 删除操作，删除第i个结点</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">DataType LinkList&lt;DataType&gt;::<span class="built_in">Delete</span>(<span class="type">int</span> i) &#123;</span><br><span class="line">	<span class="keyword">if</span> (i &lt; <span class="number">1</span> || i &gt; <span class="keyword">this</span>-&gt;<span class="built_in">Length</span>()) <span class="keyword">throw</span> <span class="string">&quot;位置错误&quot;</span>;</span><br><span class="line"></span><br><span class="line">	DataType del = <span class="keyword">this</span>-&gt;<span class="built_in">Get</span>(i);</span><br><span class="line"></span><br><span class="line">	Node&lt;DataType&gt;* node = header, *temp = <span class="literal">nullptr</span>;</span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; i - <span class="number">1</span>; j++) &#123;</span><br><span class="line">		node = node-&gt;next;</span><br><span class="line">	&#125;</span><br><span class="line">	temp = node-&gt;next;</span><br><span class="line">	node-&gt;next = node-&gt;next-&gt;next;</span><br><span class="line">	<span class="built_in">delete</span>(temp);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> del;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 判断线性表是否为空</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">int</span> LinkList&lt;DataType&gt;::<span class="built_in">Empty</span>() &#123;</span><br><span class="line">	<span class="keyword">if</span> (<span class="keyword">this</span>-&gt;header-&gt;next == <span class="literal">nullptr</span>) &#123;</span><br><span class="line">		<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 遍历操作，按序号依次输出各结点</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">void</span> LinkList&lt;DataType&gt;::<span class="built_in">PrintList</span>() &#123;</span><br><span class="line">	<span class="keyword">if</span> (<span class="keyword">this</span>-&gt;<span class="built_in">Empty</span>()) &#123;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;&#123;&#125;&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	Node&lt;DataType&gt;* temp = header-&gt;next;</span><br><span class="line"></span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;&#123;&quot;</span> &lt;&lt; temp-&gt;data;</span><br><span class="line">	<span class="keyword">while</span> (temp-&gt;next != <span class="literal">nullptr</span>) &#123;</span><br><span class="line">		temp = temp-&gt;next;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;,&quot;</span> &lt;&lt; temp-&gt;data;</span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt;  <span class="string">&quot;&#125;&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><p><strong>Main.h</strong></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&quot;LinkList.h&quot;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 菜单</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType = <span class="type">int</span>&gt;</span><br><span class="line"><span class="type">void</span> <span class="built_in">Menu</span>(<span class="type">int</span> choose, LinkList&lt;&gt;* list);</span><br><span class="line"><span class="comment">// 清除控制台（未使用）</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Clear</span><span class="params">()</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> init[] = &#123; <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span> &#125;;</span><br><span class="line">	LinkList&lt;&gt; <span class="built_in">list</span>(init, <span class="number">8</span>);</span><br><span class="line">	<span class="type">int</span> choose = <span class="number">-1</span>;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">while</span> (choose) &#123;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;--------------------------------&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;元素[&quot;</span> &lt;&lt; list.<span class="built_in">Length</span>() &lt;&lt; <span class="string">&quot;]个|单链表状态&quot;</span>;</span><br><span class="line">		list.<span class="built_in">PrintList</span>();</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;1、插入一个数字&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;2、指定位置插入一个数字&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;3、获取某个数的具体位置&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;4、获取一个具体位置的数&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;5、删除一个指定位置的数&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;0、退出演示&quot;</span> &lt;&lt; endl;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入对应服务编号：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; choose;</span><br><span class="line">		<span class="keyword">try</span> &#123;</span><br><span class="line">			<span class="built_in">Menu</span>(choose, &amp;list);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">catch</span> (<span class="type">const</span> <span class="type">char</span>* e) &#123;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;出错啦，错误消息：&quot;</span> &lt;&lt; e &lt;&lt; endl;</span><br><span class="line">		&#125;</span><br><span class="line">		cout &lt;&lt; endl &lt;&lt; <span class="string">&quot;--------------------------------&quot;</span> &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 菜单</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType = <span class="type">int</span>&gt;</span><br><span class="line"><span class="type">void</span> <span class="built_in">Menu</span>(<span class="type">int</span> choose, LinkList&lt;&gt;* list) &#123;</span><br><span class="line">	<span class="type">int</span> in_1 = <span class="number">0</span>, in_2 = <span class="number">0</span>, temp_1 = <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">switch</span> (choose) &#123;</span><br><span class="line">		<span class="comment">// 插入一个数字</span></span><br><span class="line">	<span class="keyword">case</span> <span class="number">1</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入要插入的数字：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; in_1;</span><br><span class="line">		list-&gt;<span class="built_in">Insert</span>(list-&gt;<span class="built_in">Length</span>() + <span class="number">1</span>, in_1);</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">		<span class="comment">// 指定位置插入一个数字</span></span><br><span class="line">	<span class="keyword">case</span> <span class="number">2</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入指定位置与要插入的数字：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; in_1 &gt;&gt; in_2;</span><br><span class="line">		list-&gt;<span class="built_in">Insert</span>(in_1, in_2);</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">		<span class="comment">// 获取某个数的具体位置</span></span><br><span class="line">	<span class="keyword">case</span> <span class="number">3</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入要查询的数：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; in_1;</span><br><span class="line">		temp_1 = list-&gt;<span class="built_in">Locate</span>(in_1);</span><br><span class="line">		<span class="keyword">if</span> (temp_1) &#123;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;所查数第一次出现的位置是：&quot;</span> &lt;&lt; temp_1 &lt;&lt; endl;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;没有查到哦~&quot;</span> &lt;&lt; endl;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">		<span class="comment">// 获取一个具体位置的数</span></span><br><span class="line">	<span class="keyword">case</span> <span class="number">4</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入要查找的位置：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; in_1;</span><br><span class="line">		temp_1 = list-&gt;<span class="built_in">Get</span>(in_1);</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;所在位置的数是：&quot;</span> &lt;&lt; temp_1 &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">		<span class="comment">// 删除一个指定位置的数</span></span><br><span class="line">	<span class="keyword">case</span> <span class="number">5</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入要删除的位置：&quot;</span>;</span><br><span class="line">		cin &gt;&gt; in_1;</span><br><span class="line">		list-&gt;<span class="built_in">Delete</span>(in_1);</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">	<span class="keyword">case</span> <span class="number">0</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;感谢体验，再见~&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">break</span>;</span><br><span class="line">	<span class="keyword">default</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;输入有误&quot;</span> &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 清除屏幕（未使用）</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Clear</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;\x1B[2J\x1B[H&quot;</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><p>运行效果和顺序表差不多，就不过多展示了</p><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/image-20230318123337905.png" alt="image-20230318123337905"></p><h3 id="顺序栈"><a href="#顺序栈" class="headerlink" title="顺序栈"></a>顺序栈</h3><p>栈结构就是先入后出，后入先出，使用顺序栈实现四则运算</p><p><strong>MyMath.h</strong></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">pragma</span> once</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 判断运算符优先级</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">Precedence</span><span class="params">(<span class="type">char</span> op)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 根据二元运算符运算</span></span><br><span class="line"><span class="function"><span class="type">float</span> <span class="title">Operate</span><span class="params">(<span class="type">float</span> left, <span class="type">float</span> right, <span class="type">char</span> op)</span></span>;</span><br></pre></td></tr></table></figure><p><strong>SeqStack.h</strong></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">pragma</span> once</span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> StackSize = <span class="number">10</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType = <span class="type">int</span>&gt;</span><br><span class="line"><span class="keyword">class</span> SeqStack &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="built_in">SeqStack</span>();					<span class="comment">// 构造函数</span></span><br><span class="line">	~<span class="built_in">SeqStack</span>();				<span class="comment">// 析构函数</span></span><br><span class="line">	<span class="function"><span class="type">void</span> <span class="title">Push</span><span class="params">(DataType x)</span></span>;		<span class="comment">// 入栈操作</span></span><br><span class="line">	<span class="function">DataType <span class="title">Pop</span><span class="params">()</span></span>;				<span class="comment">// 出栈操作</span></span><br><span class="line">	<span class="function">DataType <span class="title">GetTop</span><span class="params">()</span></span>;			<span class="comment">// 去栈顶元素</span></span><br><span class="line">	<span class="function"><span class="type">int</span> <span class="title">Empty</span><span class="params">()</span></span>;				<span class="comment">// 判断栈是否为空</span></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">	DataType data[StackSize];	<span class="comment">// 存放栈元素的数组</span></span><br><span class="line">	<span class="type">int</span> top;					<span class="comment">// 栈顶元素在数组中的下标</span></span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 构造函数</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">SeqStack&lt;DataType&gt;::<span class="built_in">SeqStack</span>() &#123;</span><br><span class="line">	<span class="keyword">this</span>-&gt;top = <span class="number">-1</span>;	<span class="comment">// 初始化栈顶元素下标</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 析构函数</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">SeqStack&lt;DataType&gt;::~<span class="built_in">SeqStack</span>() &#123;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 入栈</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">void</span> SeqStack&lt;DataType&gt;::<span class="built_in">Push</span>(DataType x) &#123;</span><br><span class="line">	<span class="keyword">if</span> (<span class="keyword">this</span>-&gt;top == StackSize - <span class="number">1</span>) <span class="keyword">throw</span> <span class="string">&quot;栈溢出&quot;</span>;</span><br><span class="line">	<span class="keyword">this</span>-&gt;data[++top] = x;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 出栈</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">DataType SeqStack&lt;DataType&gt;::<span class="built_in">Pop</span>() &#123;</span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">this</span>-&gt;data[<span class="keyword">this</span>-&gt;top--];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 取栈顶</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">DataType SeqStack&lt;DataType&gt;::<span class="built_in">GetTop</span>() &#123;</span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">this</span>-&gt;data[<span class="keyword">this</span>-&gt;top];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 判断栈是否为空</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">int</span> SeqStack&lt;DataType&gt;::<span class="built_in">Empty</span>() &#123;</span><br><span class="line">	<span class="keyword">return</span> (<span class="keyword">this</span>-&gt;top == <span class="number">-1</span>) ? <span class="number">1</span> : <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><p><strong>MyMath.cpp</strong></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&quot;MyMath.h&quot;</span></span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 判断运算符优先级</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">Precedence</span><span class="params">(<span class="type">char</span> op)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">switch</span> (op) &#123;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;(&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;#&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;=&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;+&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;-&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;*&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> <span class="number">3</span>;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;/&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> <span class="number">3</span>;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;)&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> <span class="number">4</span>;</span><br><span class="line">	<span class="keyword">default</span>:</span><br><span class="line">		<span class="keyword">throw</span> <span class="string">&quot;不支持的运算符&quot;</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 根据二元运算符运算</span></span><br><span class="line"><span class="function"><span class="type">float</span> <span class="title">Operate</span><span class="params">(<span class="type">float</span> left, <span class="type">float</span> right, <span class="type">char</span> op)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">switch</span> (op) &#123;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;+&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> left + right;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;-&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> left - right;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;*&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> left * right;</span><br><span class="line">	<span class="keyword">case</span> <span class="string">&#x27;/&#x27;</span>:</span><br><span class="line">		<span class="keyword">return</span> left / right;</span><br><span class="line">	<span class="keyword">default</span>:</span><br><span class="line">		<span class="keyword">throw</span> <span class="string">&quot;不支持的运算符&quot;</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p><strong>Main.cpp</strong></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&quot;SeqStack.h&quot;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&quot;MyMath.h&quot;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;string&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	string allOps = <span class="string">&quot;#+-*/=()&quot;</span>, userIn = <span class="string">&quot;&quot;</span>;	<span class="comment">// 定义所有支持的运算符与用户输入</span></span><br><span class="line">	SeqStack&lt;<span class="type">float</span>&gt; nums;						<span class="comment">// 用于存储运算数</span></span><br><span class="line">	SeqStack&lt;<span class="type">char</span>&gt; ops;						<span class="comment">// 用于存储运算符</span></span><br><span class="line">	<span class="type">char</span> op = <span class="string">&#x27;\0&#x27;</span>;</span><br><span class="line">	<span class="type">float</span> num = <span class="number">0</span>, left = <span class="number">0</span>, right = <span class="number">0</span>;		<span class="comment">// 用于存储程序会产生的数字</span></span><br><span class="line">	ops.<span class="built_in">Push</span>(<span class="string">&#x27;#&#x27;</span>);							<span class="comment">// 将结束符号压入栈中，方便优先级比较</span></span><br><span class="line">	</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入你的表达式\n每次输入[运算数]or[运算符]&quot;</span> &lt;&lt; endl;</span><br><span class="line">	<span class="keyword">do</span> &#123;</span><br><span class="line">		<span class="keyword">if</span> (userIn != <span class="string">&quot;=&quot;</span>) &#123;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;你的输入：&quot;</span>;</span><br><span class="line">			cin &gt;&gt; userIn;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 判断左括号</span></span><br><span class="line">		<span class="keyword">if</span> (userIn == <span class="string">&quot;(&quot;</span>) &#123;</span><br><span class="line">			ops.<span class="built_in">Push</span>(<span class="string">&#x27;(&#x27;</span>);</span><br><span class="line">			<span class="keyword">continue</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 判断是否为运算符</span></span><br><span class="line">		<span class="keyword">if</span> (allOps.<span class="built_in">find</span>(userIn) == string::npos) &#123;</span><br><span class="line">			<span class="comment">// 不是运算符则为数字，转为数字并压入数字栈</span></span><br><span class="line">			num = <span class="built_in">stof</span>(userIn);	<span class="comment">// 转为数字</span></span><br><span class="line">			nums.<span class="built_in">Push</span>(num);		<span class="comment">// 将数字压入数字栈中</span></span><br><span class="line">			<span class="keyword">continue</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 判断右括号</span></span><br><span class="line">		<span class="keyword">if</span> (userIn == <span class="string">&quot;)&quot;</span>) &#123;</span><br><span class="line">			<span class="keyword">while</span> ((op = ops.<span class="built_in">Pop</span>()) != <span class="string">&#x27;(&#x27;</span>) &#123;</span><br><span class="line">				right = nums.<span class="built_in">Pop</span>();</span><br><span class="line">				left = nums.<span class="built_in">Pop</span>();</span><br><span class="line">				nums.<span class="built_in">Push</span>(<span class="built_in">Operate</span>(left, right, op));</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">continue</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 判断运算符优先级</span></span><br><span class="line">		<span class="keyword">if</span> (<span class="built_in">Precedence</span>(ops.<span class="built_in">GetTop</span>()) &gt;= <span class="built_in">Precedence</span>(userIn[<span class="number">0</span>])) &#123;</span><br><span class="line">			<span class="comment">// 如果新运算的优先级比栈中低则先弹栈进行运算</span></span><br><span class="line">			right = nums.<span class="built_in">Pop</span>();</span><br><span class="line">			left = nums.<span class="built_in">Pop</span>();</span><br><span class="line">			nums.<span class="built_in">Push</span>(<span class="built_in">Operate</span>(left, right, ops.<span class="built_in">Pop</span>()));	<span class="comment">// 将运算结果压入数字栈中</span></span><br><span class="line">			<span class="comment">// 将用户输入的运算符压入运算符栈中</span></span><br><span class="line">			<span class="keyword">if</span> (userIn != <span class="string">&quot;=&quot;</span>) &#123;</span><br><span class="line">				ops.<span class="built_in">Push</span>(userIn[<span class="number">0</span>]);</span><br><span class="line">			&#125;						</span><br><span class="line">			<span class="keyword">continue</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		<span class="comment">// 如果新运算的优先级比栈中高则直接压入运算符栈</span></span><br><span class="line">		<span class="keyword">if</span> (userIn != <span class="string">&quot;=&quot;</span>) &#123;</span><br><span class="line">			ops.<span class="built_in">Push</span>(userIn[<span class="number">0</span>]);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125; <span class="keyword">while</span> (userIn != <span class="string">&quot;=&quot;</span> || ops.<span class="built_in">GetTop</span>() != <span class="string">&#x27;#&#x27;</span>);</span><br><span class="line"></span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;计算结果：&quot;</span> &lt;&lt; nums.<span class="built_in">GetTop</span>();</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p>运行效果</p><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/image-20230406202708597.png" alt="image-20230406202708597"></p><h3 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h3><p>先入先出，后入后出，这里使用循环队列完成了一个门诊看病的案例</p><p><strong>CirQueue.h</strong></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">pragma</span> once</span></span><br><span class="line"></span><br><span class="line"><span class="type">const</span> <span class="type">int</span> QueueSize = <span class="number">50</span>;		<span class="comment">// 设置循环队列的长度</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="keyword">class</span> <span class="title class_">CirQueue</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">	<span class="built_in">CirQueue</span>();					<span class="comment">// 构造函数</span></span><br><span class="line">	~<span class="built_in">CirQueue</span>();				<span class="comment">// 析构函数</span></span><br><span class="line">	<span class="function"><span class="type">void</span> <span class="title">EnQueue</span><span class="params">(DataType x)</span></span>;	<span class="comment">// 入队操作，将元素x入队</span></span><br><span class="line">	<span class="function">DataType <span class="title">DeQueue</span><span class="params">()</span></span>;			<span class="comment">// 出队操作</span></span><br><span class="line">	<span class="function">DataType <span class="title">GetHead</span><span class="params">()</span></span>;			<span class="comment">// 取队头元素</span></span><br><span class="line">	<span class="function"><span class="type">int</span> <span class="title">Empty</span><span class="params">()</span></span>;				<span class="comment">// 判空</span></span><br><span class="line">	<span class="function"><span class="type">int</span> <span class="title">Size</span><span class="params">()</span></span>;					<span class="comment">// 长度</span></span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">	DataType data[QueueSize];	<span class="comment">// 数据</span></span><br><span class="line">	<span class="type">int</span> start, end, length;		<span class="comment">// 队头和队尾以及长度</span></span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 长度</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">int</span> CirQueue&lt;DataType&gt;::<span class="built_in">Size</span>() &#123;</span><br><span class="line">	<span class="keyword">return</span> length;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 构造函数</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">CirQueue&lt;DataType&gt;::<span class="built_in">CirQueue</span>() &#123;</span><br><span class="line">	<span class="comment">// 将头尾都指向最后一个位置</span></span><br><span class="line">	<span class="keyword">this</span>-&gt;start = QueueSize - <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">this</span>-&gt;end = QueueSize - <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">this</span>-&gt;length = <span class="number">0</span>;	<span class="comment">// 长度为0</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 析构函数</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">CirQueue&lt;DataType&gt;::~<span class="built_in">CirQueue</span>() &#123;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 入队</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">void</span> CirQueue&lt;DataType&gt;::<span class="built_in">EnQueue</span>(DataType x) &#123;</span><br><span class="line">	<span class="keyword">if</span> ((<span class="keyword">this</span>-&gt;end + <span class="number">1</span>) % QueueSize == <span class="keyword">this</span>-&gt;start) <span class="keyword">throw</span> <span class="string">&quot;满&quot;</span>;</span><br><span class="line">	<span class="keyword">this</span>-&gt;data[<span class="keyword">this</span>-&gt;end = ((<span class="keyword">this</span>-&gt;end + <span class="number">1</span>) % QueueSize)] = x;</span><br><span class="line">	<span class="keyword">this</span>-&gt;length++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 出队</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">DataType CirQueue&lt;DataType&gt;::<span class="built_in">DeQueue</span>() &#123;</span><br><span class="line">	<span class="keyword">this</span>-&gt;length--;</span><br><span class="line">	<span class="keyword">if</span> (<span class="keyword">this</span>-&gt;start == <span class="keyword">this</span>-&gt;end) <span class="keyword">throw</span> <span class="string">&quot;空队&quot;</span>;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">this</span>-&gt;data[<span class="keyword">this</span>-&gt;start = (<span class="keyword">this</span>-&gt;start + <span class="number">1</span>) % QueueSize];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 取队头</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line">DataType CirQueue&lt;DataType&gt;::<span class="built_in">GetHead</span>() &#123;</span><br><span class="line">	<span class="keyword">if</span> (<span class="keyword">this</span>-&gt;start == <span class="keyword">this</span>-&gt;end) <span class="keyword">throw</span> <span class="string">&quot;空队&quot;</span>;</span><br><span class="line">	<span class="keyword">return</span> <span class="keyword">this</span>-&gt;data[(<span class="keyword">this</span>-&gt;start + <span class="number">1</span>) % QueueSize];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 判空</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> DataType&gt;</span><br><span class="line"><span class="type">int</span> CirQueue&lt;DataType&gt;::<span class="built_in">Empty</span>() &#123;</span><br><span class="line">	<span class="keyword">return</span> length ? <span class="number">0</span> : <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p><strong>Main.cpp</strong></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&quot;CirQueue.h&quot;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;string&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 用于存储病人信息的结构体</span></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Sick</span> &#123;</span><br><span class="line">	string id;	<span class="comment">// 编号</span></span><br><span class="line">	string name;<span class="comment">// 姓名</span></span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">	处理菜单选项，并返回进入门诊的人</span></span><br><span class="line"><span class="comment">	choice：选项</span></span><br><span class="line"><span class="comment">	sicks：排队的病人</span></span><br><span class="line"><span class="comment">	current：当前正在门诊的病人</span></span><br><span class="line"><span class="comment">	return：返回处理后正在门诊的病人</span></span><br><span class="line"><span class="comment">*/</span> </span><br><span class="line"><span class="function">Sick* <span class="title">choiceHandle</span><span class="params">(<span class="type">int</span> choice, CirQueue&lt;Sick*&gt;* sicks, Sick* current)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="type">int</span> userIn = <span class="number">0</span>;</span><br><span class="line">	CirQueue&lt;Sick*&gt;* sicks = <span class="keyword">new</span> CirQueue&lt;Sick*&gt;;</span><br><span class="line">	<span class="keyword">struct</span> <span class="title class_">Sick</span>* sick = <span class="literal">nullptr</span>;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">do</span> &#123;</span><br><span class="line">		<span class="keyword">try</span> &#123;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;----------输入数字选择对应功能----------&quot;</span> &lt;&lt; endl;</span><br><span class="line">			<span class="keyword">if</span> (sick == <span class="literal">nullptr</span>) &#123;</span><br><span class="line">				cout &lt;&lt; <span class="string">&quot;----------------诊室空闲----------------&quot;</span> &lt;&lt; endl;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span> &#123;</span><br><span class="line">				cout &lt;&lt; <span class="string">&quot;---编号[&quot;</span> + sick-&gt;id + <span class="string">&quot;]|姓名[&quot;</span> + sick-&gt;name + <span class="string">&quot;]正在门诊-----&quot;</span> &lt;&lt; endl;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">if</span> (sicks-&gt;<span class="built_in">Size</span>()) &#123;</span><br><span class="line">				cout &lt;&lt; <span class="string">&quot;---请编号[&quot;</span> + sicks-&gt;<span class="built_in">GetHead</span>()-&gt;id + <span class="string">&quot;]|姓名[&quot;</span> + sicks-&gt;<span class="built_in">GetHead</span>()-&gt;name + <span class="string">&quot;]做好准备-----&quot;</span> &lt;&lt; endl;</span><br><span class="line">			&#125;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;---------当前还有[&quot;</span> &lt;&lt; sicks-&gt;<span class="built_in">Size</span>() &lt;&lt; <span class="string">&quot;]人正在排队----------&quot;</span> &lt;&lt; endl;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;--------------1、录入病人---------------&quot;</span> &lt;&lt; endl;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;--------------2、呼叫病人---------------&quot;</span> &lt;&lt; endl;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;--------------0、退出系统---------------&quot;</span> &lt;&lt; endl;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;请选择：&quot;</span>;</span><br><span class="line">			cin &gt;&gt; userIn;</span><br><span class="line">			sick = <span class="built_in">choiceHandle</span>(userIn, sicks, sick);</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;----------------------------------------&quot;</span> &lt;&lt; endl;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">catch</span> (<span class="type">const</span> <span class="type">char</span>* ex) &#123;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;错误的操作&quot;</span> &lt;&lt; endl;</span><br><span class="line">			<span class="built_in">exit</span>(<span class="number">-1</span>);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125; <span class="keyword">while</span> (userIn);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">	处理菜单选项，并返回进入门诊的人</span></span><br><span class="line"><span class="comment">	choice：选项</span></span><br><span class="line"><span class="comment">	sicks：排队的病人</span></span><br><span class="line"><span class="comment">	current：当前正在门诊的病人</span></span><br><span class="line"><span class="comment">	return：返回处理后正在门诊的病人</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function">Sick* <span class="title">choiceHandle</span><span class="params">(<span class="type">int</span> choice, CirQueue&lt;Sick*&gt;* sicks, Sick* current)</span> </span>&#123;</span><br><span class="line">	<span class="keyword">struct</span> <span class="title class_">Sick</span>* sick;</span><br><span class="line">	<span class="keyword">switch</span> (choice) &#123;</span><br><span class="line">	<span class="keyword">case</span> <span class="number">0</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;再见&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span> <span class="literal">nullptr</span>;</span><br><span class="line">	<span class="keyword">case</span> <span class="number">1</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;请输入编号及姓名&quot;</span> &lt;&lt; endl;</span><br><span class="line">		sick = <span class="keyword">new</span> Sick;</span><br><span class="line">		cin &gt;&gt; sick-&gt;id &gt;&gt; sick-&gt;name;</span><br><span class="line">		sicks-&gt;<span class="built_in">EnQueue</span>(sick);</span><br><span class="line">		<span class="keyword">return</span> current;</span><br><span class="line">	<span class="keyword">case</span> <span class="number">2</span>:</span><br><span class="line">		<span class="keyword">if</span> (sicks-&gt;<span class="built_in">Size</span>()) &#123;</span><br><span class="line">			sick = sicks-&gt;<span class="built_in">DeQueue</span>();</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			cout &lt;&lt; <span class="string">&quot;无人等待&quot;</span> &lt;&lt; endl;</span><br><span class="line">			sick = <span class="literal">nullptr</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> sick;</span><br><span class="line">	<span class="keyword">default</span>:</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;不支持的选项&quot;</span> &lt;&lt; endl;</span><br><span class="line">		<span class="keyword">return</span> current;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p>运行截图</p><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/image-20230406203204850.png" alt="image-20230406203204850"></p><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/image-20230406203226150.png" alt="image-20230406203226150"></p><h3 id="模式匹配"><a href="#模式匹配" class="headerlink" title="模式匹配"></a>模式匹配</h3><p>字符串特有的功能</p><h4 id="BF"><a href="#BF" class="headerlink" title="BF"></a>BF</h4><p>暴力算法</p><p><strong>Main.cpp</strong></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">* 获取子串在主串中第一次出现的起始位置，不存在则返回0</span></span><br><span class="line"><span class="comment">* param s 主串</span></span><br><span class="line"><span class="comment">* param t 子串</span></span><br><span class="line"><span class="comment">* return 返回子串在主串中第一次出现的下标（从1起标），不存在则返回0</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">BF</span><span class="params">(<span class="type">char</span>* s, <span class="type">char</span>* t)</span> </span>&#123;</span><br><span class="line">    <span class="type">int</span> start = <span class="number">0</span>;                              <span class="comment">// 设置主串每次匹配的起始位置</span></span><br><span class="line">    <span class="type">int</span> i = <span class="number">0</span>, j = <span class="number">0</span>;                           <span class="comment">// i记录主串某次匹配的位置变动，j记录子串匹配的位置变动</span></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">        当主串下标不为空时说明主串还没匹配完，</span></span><br><span class="line"><span class="comment">        当子串下标不为空时说明子串还没被匹配完过</span></span><br><span class="line"><span class="comment">        当上面两个条件同时满足才执行循环</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">    <span class="keyword">while</span> ((s[i] != <span class="string">&#x27;\0&#x27;</span>) &amp;&amp; (t[j] != <span class="string">&#x27;\0&#x27;</span>)) &#123;</span><br><span class="line">        <span class="comment">/*</span></span><br><span class="line"><span class="comment">            如果在某次匹配中，子串能与主串匹配上就一直往下匹配，</span></span><br><span class="line"><span class="comment">            直到主串到底，或者子串到底</span></span><br><span class="line"><span class="comment">            主串到底说明已经没法匹配了</span></span><br><span class="line"><span class="comment">            子串到底说明找到了子串在主串中的位置</span></span><br><span class="line"><span class="comment">        */</span></span><br><span class="line">        <span class="keyword">if</span> (s[i] == t[j]) &#123;</span><br><span class="line">            i++;</span><br><span class="line">            j++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">/*</span></span><br><span class="line"><span class="comment">            如果某次匹配没有匹配上，就说明主串的这个位置匹配不上，</span></span><br><span class="line"><span class="comment">            匹配的主串起始位置就往下走一位，</span></span><br><span class="line"><span class="comment">            并将记录主串某次匹配的位置更新为主串新的匹配起始位置，</span></span><br><span class="line"><span class="comment">            记录子串匹配的位置初始化为子串的第一个字符位置</span></span><br><span class="line"><span class="comment">        */</span></span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            start++; </span><br><span class="line">            i = start; </span><br><span class="line">            j = <span class="number">0</span>; </span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/*</span></span><br><span class="line"><span class="comment">        当匹配完成后如果子串的下标匹配记录为\0，</span></span><br><span class="line"><span class="comment">        则说明子串匹配成功了，就返回最后这次匹配的主串起始位置+1（方法返回从1起标）。</span></span><br><span class="line"><span class="comment">        如果子串下标匹配记录不为\0，说明是主串的下标匹配记录为\0，</span></span><br><span class="line"><span class="comment">        表明主串已经匹配到最后一个字符了，也没有匹配到子串，就返回0，表示没有找到子串</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">    <span class="keyword">if</span> (t[j] == <span class="string">&#x27;\0&#x27;</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> start + <span class="number">1</span>; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> &#123; </span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 给两个字符指针分配内存，方便存字符串</span></span><br><span class="line">    <span class="type">char</span> *s = (<span class="type">char</span>*) <span class="built_in">malloc</span>(<span class="number">1024</span>), * t = (<span class="type">char</span>*)<span class="built_in">malloc</span>(<span class="number">1024</span>);</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 输入</span></span><br><span class="line">    cout &lt;&lt; <span class="string">&quot;请输入主串：&quot;</span>;</span><br><span class="line">    cin &gt;&gt; s;</span><br><span class="line">    cout &lt;&lt; <span class="string">&quot;请输入子串：&quot;</span>;</span><br><span class="line">    cin &gt;&gt; t;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (<span class="type">int</span> index = <span class="built_in">BF</span>(s,t)) &#123;</span><br><span class="line">        cout &lt;&lt; <span class="string">&quot;子串第一次在主串中出现的下标是：&quot;</span> &lt;&lt; index;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> &#123;</span><br><span class="line">        cout &lt;&lt; <span class="string">&quot;没有匹配到子串&quot;</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 内存释放</span></span><br><span class="line">    <span class="built_in">free</span>(s);</span><br><span class="line">    <span class="built_in">free</span>(t);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><p>运行截图</p><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/image-20230406203523753.png" alt="image-20230406203523753"></p><h4 id="KMP"><a href="#KMP" class="headerlink" title="KMP"></a>KMP</h4><p>对我来说很烧脑，我这里的实现有问题，但是能力只能先这样了</p><p><strong>Main.cpp</strong></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 用于装载数组</span></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Arr</span> &#123;</span><br><span class="line">	<span class="type">int</span>* data;	<span class="comment">// 数组指针</span></span><br><span class="line">	<span class="type">int</span> length;	<span class="comment">// 数组长度</span></span><br><span class="line">&#125;;</span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">	获取子串的next数组</span></span><br><span class="line"><span class="comment">	param t 子串的首地址</span></span><br><span class="line"><span class="comment">	return 返回next数组</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function">Arr* <span class="title">getNext</span><span class="params">(<span class="type">char</span>* t)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">	通过KMP算法获取子串在主串中第一次出现的下标（从0起标），未找到返回-1</span></span><br><span class="line"><span class="comment">	param s 主串</span></span><br><span class="line"><span class="comment">	param t 子串</span></span><br><span class="line"><span class="comment">	return 子串在主串中第一次出现的下标（从0起标），未找到返回-1</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">KMP</span><span class="params">(<span class="type">char</span>* s, <span class="type">char</span>* t)</span></span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 创建字符串接收变量</span></span><br><span class="line">	<span class="type">char</span>* s = (<span class="type">char</span>*) <span class="built_in">malloc</span>(<span class="number">1024</span>);</span><br><span class="line">	<span class="type">char</span>* t = (<span class="type">char</span>*)<span class="built_in">malloc</span>(<span class="number">1024</span>);</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 终端输入</span></span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入主串：&quot;</span>;</span><br><span class="line">	cin &gt;&gt; s;</span><br><span class="line">	cout &lt;&lt; <span class="string">&quot;请输入子串：&quot;</span>;</span><br><span class="line">	cin &gt;&gt; t;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 输出结果</span></span><br><span class="line">	<span class="type">int</span> index = <span class="built_in">KMP</span>(s, t);</span><br><span class="line">	<span class="keyword">if</span> (index == <span class="number">-1</span>) &#123;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;没有在主串中找到子串&quot;</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> &#123;</span><br><span class="line">		cout &lt;&lt; <span class="string">&quot;子串在主串中第一次出现的下标为：&quot;</span> &lt;&lt; index;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">// 释放内存</span></span><br><span class="line">	<span class="built_in">free</span>(s);</span><br><span class="line">	<span class="built_in">free</span>(t);</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">	获取子串的next数组</span></span><br><span class="line"><span class="comment">	param t 子串的首地址</span></span><br><span class="line"><span class="comment">	return 返回next数组</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function">Arr* <span class="title">getNext</span><span class="params">(<span class="type">char</span>* t)</span> </span>&#123;</span><br><span class="line">	Arr* next = <span class="keyword">new</span> Arr&#123; <span class="literal">nullptr</span>,<span class="number">0</span> &#125;;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 计算数组长度</span></span><br><span class="line">	<span class="keyword">while</span> (t[next-&gt;length] != <span class="string">&#x27;\0&#x27;</span>) &#123;</span><br><span class="line">		next-&gt;length++;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 给next数组分配空间</span></span><br><span class="line">	next-&gt;data = (<span class="type">int</span>*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">int</span>) * (next-&gt;length));</span><br><span class="line"></span><br><span class="line">	next-&gt;data[<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">	next-&gt;data[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 循环对应子串的每个字符下标</span></span><br><span class="line">	<span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">2</span>; i &lt; next-&gt;length; i++) &#123;</span><br><span class="line">		<span class="type">int</span> max = i - <span class="number">1</span>;	<span class="comment">// 当前子串字符下标需要比对的前后缀的最长长度</span></span><br><span class="line">		next-&gt;data[i] = <span class="number">0</span>;	<span class="comment">// 假想没有前后缀</span></span><br><span class="line">		<span class="comment">// 根据前后缀最大长度，从最大前后缀一直比较到最小前后缀，找到下次对比子串的起始指针</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> j = max; j &gt;= <span class="number">1</span>; j--) &#123;</span><br><span class="line">			<span class="type">int</span> flag = <span class="literal">true</span>;</span><br><span class="line">			<span class="comment">// 比较前后缀</span></span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> k = <span class="number">0</span>; k &lt; j; k++) &#123;</span><br><span class="line">				<span class="comment">// 依次比较前后缀，如果没配对就表示本次循环的前后缀长度不是最长的</span></span><br><span class="line">				<span class="keyword">if</span> (t[k] != t[max - j + k + <span class="number">1</span>]) &#123;</span><br><span class="line">					flag = <span class="literal">false</span>;</span><br><span class="line">					<span class="keyword">break</span>;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="comment">// 如果flag为真，则写入偏移量，并结束找最大前后缀</span></span><br><span class="line">			<span class="keyword">if</span> (flag) &#123;</span><br><span class="line">				<span class="comment">// 将最大前后缀长度赋值给next数组并退出</span></span><br><span class="line">				next-&gt;data[i] = j;</span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">return</span> next;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">	通过KMP算法获取子串在主串中第一次出现的下标（从0起标），未找到返回-1</span></span><br><span class="line"><span class="comment">	param s 主串</span></span><br><span class="line"><span class="comment">	param t 子串</span></span><br><span class="line"><span class="comment">	return 子串在主串中第一次出现的下标（从0起标），未找到返回-1</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">KMP</span><span class="params">(<span class="type">char</span>* s, <span class="type">char</span>* t)</span> </span>&#123;</span><br><span class="line">	<span class="comment">// 获取子串的next数组</span></span><br><span class="line">	Arr* next = <span class="built_in">getNext</span>(t);</span><br><span class="line">	<span class="comment">// 分别为主串的比较下标记录与子串的比较下标记录</span></span><br><span class="line">	<span class="type">int</span> start = <span class="number">0</span>, t_i = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 当主串比较到完，或者子串比较完就终止循环</span></span><br><span class="line">	<span class="comment">// 子串比较完说明找到了子串的下标，主串比较完说明没有找到</span></span><br><span class="line">	<span class="keyword">while</span> (s[start] != <span class="string">&#x27;\0&#x27;</span> &amp;&amp; t[t_i] != <span class="string">&#x27;\0&#x27;</span>) &#123;</span><br><span class="line">		<span class="keyword">if</span> (s[start] == t[t_i]) &#123;</span><br><span class="line">			t_i++;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> &#123;</span><br><span class="line">			t_i = next-&gt;data[t_i + <span class="number">1</span>];</span><br><span class="line">		&#125;</span><br><span class="line">		start++;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 子串比较完说明找到了子串的下标</span></span><br><span class="line">	<span class="keyword">if</span> (t[t_i] == <span class="string">&#x27;\0&#x27;</span>) &#123;</span><br><span class="line">		<span class="comment">// 返回子串第一次出现的下标</span></span><br><span class="line">		<span class="comment">// 由于主串下标在比较时会往后走，所以返回时要减去子串的长度</span></span><br><span class="line">		<span class="keyword">return</span> start - next-&gt;length;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="comment">// 子串没有比较完说明没有在主串中找到子串，返回-1</span></span><br><span class="line">	<span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><p>运行截图</p><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/knowledge/data-structure/image-20230406203822526.png" alt="image-20230406203822526"></p><h2 id="扩展"><a href="#扩展" class="headerlink" title="扩展"></a>扩展</h2><ul><li>双向链表：一个结点包含前驱与后继的结点指针</li><li>循环链表：<ul><li>单链表：尾结点的后继结点指针指向头结点</li><li>双向链表：头结点的前驱结点指针指向尾结点，尾结点的后继结点指针指向头结点</li></ul></li></ul></article><div class="post-copyright"><div class="copyright-cc-box"><i class="anzhiyufont anzhiyu-icon-copyright"></i></div><div class="post-copyright__author_box"><a class="post-copyright__author_img" target="_blank" rel="noopener" href="https://insectmk.cn" title="头像"><img class="post-copyright__author_img_back" src="/static/img/head/insectmk.jpg" title="头像" alt="头像"><img class="post-copyright__author_img_front" src="/static/img/head/insectmk.jpg" title="头像" alt="头像"></a><div class="post-copyright__author_name">InsectMk</div><div class="post-copyright__author_desc">今天特别开心！</div></div><div class="post-copyright__post__info"><a class="post-copyright__original" title="该文章为原创文章，注意版权协议" href="https://insectmk.top/posts/79666db/">原创</a><a class="post-copyright-title"><span onclick='rm.copyPageUrl("https://insectmk.top/posts/79666db/")'>数据结构</span></a></div><div class="post-tools" id="post-tools"><div class="post-tools-left"><div class="rewardLeftButton"></div><div class="shareRight"><div class="share-link mobile"><div class="share-qrcode"><div class="share-button" title="使用手机访问这篇文章"><i class="anzhiyufont anzhiyu-icon-qrcode"></i></div><div class="share-main"><div class="share-main-all"><div id="qrcode" title="https://insectmk.top/posts/79666db/"></div><div class="reward-dec">使用手机访问这篇文章</div></div></div></div></div><div class="share-link weibo"><a class="share-button" target="_blank" href="https://service.weibo.com/share/share.php?title=undefined&amp;url=https://insectmk.top/posts/79666db/&amp;pic=undefined" rel="external nofollow noreferrer noopener"><i class="anzhiyufont anzhiyu-icon-weibo"></i></a></div><script>function copyCurrentPageUrl(){var e=window.location.href,t=document.createElement("input");t.setAttribute("value",e),document.body.appendChild(t),t.select(),t.setSelectionRange(0,99999),document.execCommand("copy"),document.body.removeChild(t)}</script><div class="share-link copyurl"><div class="share-button" id="post-share-url" title="复制链接" onclick="copyCurrentPageUrl()"><i class="anzhiyufont anzhiyu-icon-link"></i></div></div></div></div></div><div class="post-copyright__notice"><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://insectmk.top" target="_blank">InsectMk的个人空间</a>！</span></div></div><div class="post-tools-right"><div class="tag_share"><div class="post-meta__box"><div class="post-meta__box__tag-list"><a class="post-meta__box__tags" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"><span class="tags-punctuation"><i class="anzhiyufont anzhiyu-icon-tag"></i></span>数据结构<span class="tagsPageCount">1</span></a></div></div></div><div class="post_share"><div class="social-share" data-image="https://image.insectmk.cn/hexo-gitee-blog/cover/github-insectmk.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.cbd.int/butterfly-extsrc@1.1.3/sharejs/dist/css/share.min.css" media="print" onload='this.media="all"'><script src="https://cdn.cbd.int/butterfly-extsrc@1.1.3/sharejs/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/posts/edb528cc/"><img class="prev-cover" src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/review/software-construction/cover.jpg" onerror='onerror=null,src="/static/img/website/404.jpg"' alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">大三上软件构造期末复习提纲</div></div></a></div><div class="next-post pull-right"><a href="/posts/88d43a64/"><img class="next-cover" src="/" onerror='onerror=null,src="/static/img/website/404.jpg"' alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">平时在用的网站</div></div></a></div></nav><hr><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="anzhiyufont anzhiyu-icon-comments"></i><span> 评论</span></div><div class="comment-randomInfo"><a onclick="anzhiyu.addRandomCommentInfo()" href="javascript:void(0)">匿名评论</a><a href="/privacy" style="margin-left:4px">隐私政策</a></div></div><div class="comment-wrap"><div><div id="waline-wrap"></div></div></div></div><div class="comment-barrage"></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="card-content"><div class="author-info-avatar"><img class="avatar-img" src="/static/img/head/insectmk.jpg" onerror='this.onerror=null,this.src="/static/img/website/friend_404.gif"' alt="avatar"></div><div class="author-info__description"><div style="line-height:1.38;margin:.6rem 0;text-align:justify;color:rgba(255,255,255,.8)">这有关于<b style="color:#fff">程序开发、部署</b>相关的问题和看法，还有<b style="color:#fff">软件推荐</b>和<b style="color:#fff">分享</b>。</div><div style="line-height:1.38;margin:.6rem 0;text-align:justify;color:rgba(255,255,255,.8)">相信你可以在这里找到对你有用的<b style="color:#fff">知识</b>和<b style="color:#fff">教程</b>。</div></div><div class="author-info__bottom-group"><a class="author-info__bottom-group-left" href="/"><h1 class="author-info__name">InsectMk</h1><div class="author-info__desc">今天特别开心！</div></a><div class="card-info-social-icons is-center"><a class="social-icon faa-parent animated-hover" href="https://gitee.com/insectmk" target="_blank" title="Gitee"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-gitee"></use></svg></a><a class="social-icon faa-parent animated-hover" href="/static/img/website/contact/qq.png" target="_blank" title="QQ"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-qq"></use></svg></a><a class="social-icon faa-parent animated-hover" href="/static/img/website/contact/wechat.png" target="_blank" title="WeChat"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-wechat"></use></svg></a><a class="social-icon faa-parent animated-hover" href="/atom.xml" target="_blank" title="订阅-ATOM"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-rss"></use></svg></a><a class="social-icon faa-parent animated-hover" href="mailto:3067836615@qq.com" target="_blank" title="Email"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-youxiang-"></use></svg></a></div></div></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-bars"></i><span>文章目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-number">1.</span> <span class="toc-text">数据结构</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BC%95%E5%85%A5"><span class="toc-number">1.1.</span> <span class="toc-text">引入</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%BA%BF%E6%80%A7%E8%A1%A8"><span class="toc-number">1.2.</span> <span class="toc-text">线性表</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E7%BB%93%E6%9E%84"><span class="toc-number">1.2.1.</span> <span class="toc-text">顺序结构</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8D%95%E9%93%BE%E8%A1%A8"><span class="toc-number">1.2.2.</span> <span class="toc-text">单链表</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E6%A0%88"><span class="toc-number">1.2.3.</span> <span class="toc-text">顺序栈</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%98%9F%E5%88%97"><span class="toc-number">1.2.4.</span> <span class="toc-text">队列</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D"><span class="toc-number">1.2.5.</span> <span class="toc-text">模式匹配</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#BF"><span class="toc-number">1.2.5.1.</span> <span class="toc-text">BF</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#KMP"><span class="toc-number">1.2.5.2.</span> <span class="toc-text">KMP</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%89%A9%E5%B1%95"><span class="toc-number">1.3.</span> <span class="toc-text">扩展</span></a></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-history"></i><span>最近发布</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/posts/98f3f974/" title="美化你的Github个人主页"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/github-insectmk.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="美化你的Github个人主页"></a><div class="content"><a class="title" href="/posts/98f3f974/" title="美化你的Github个人主页">美化你的Github个人主页</a><time datetime="2024-07-30T02:52:23.000Z" title="发表于 2024-07-30 10:52:23">2024-07-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/10d64ca8/" title="我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/hexo-butterfly.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）"></a><div class="content"><a class="title" href="/posts/10d64ca8/" title="我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）">我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）</a><time datetime="2024-07-30T01:30:07.000Z" title="发表于 2024-07-30 09:30:07">2024-07-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/129b7f4a/" title="使用Spring AI对接Ollama搭建自己的智能问答网站"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/ollama.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="使用Spring AI对接Ollama搭建自己的智能问答网站"></a><div class="content"><a class="title" href="/posts/129b7f4a/" title="使用Spring AI对接Ollama搭建自己的智能问答网站">使用Spring AI对接Ollama搭建自己的智能问答网站</a><time datetime="2024-07-20T02:45:24.000Z" title="发表于 2024-07-20 10:45:24">2024-07-20</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/9c83ed78/" title="无需更改源码！让你的Hexo的文章在首页隐藏"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/hexo-hide-posts.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="无需更改源码！让你的Hexo的文章在首页隐藏"></a><div class="content"><a class="title" href="/posts/9c83ed78/" title="无需更改源码！让你的Hexo的文章在首页隐藏">无需更改源码！让你的Hexo的文章在首页隐藏</a><time datetime="2024-07-19T02:22:45.000Z" title="发表于 2024-07-19 10:22:45">2024-07-19</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/9348d5be/" title="使用Cloudflare加速Docker镜像下载"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/docker.png" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="使用Cloudflare加速Docker镜像下载"></a><div class="content"><a class="title" href="/posts/9348d5be/" title="使用Cloudflare加速Docker镜像下载">使用Cloudflare加速Docker镜像下载</a><time datetime="2024-06-13T08:01:10.000Z" title="发表于 2024-06-13 16:01:10">2024-06-13</time></div></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div id="workboard"><div id="runtimeTextTip"></div></div><p id="ghbdages"><a class="github-badge" target="_blank" href="https://hexo.io/" style="margin-inline:5px" data-title="博客框架为Hexo_v7.3.0" title="博客框架为Hexo_v7.3.0"><img src="https://npm.elemecdn.com/anzhiyu-blog@2.1.5/img/badge/Frame-Hexo.svg" alt="博客框架为Hexo_v7.3.0"></a><a class="github-badge" target="_blank" href="https://blog.anheyu.com/" style="margin-inline:5px" data-title="本站使用AnZhiYu主题" title="本站使用AnZhiYu主题"><img src="https://npm.elemecdn.com/anzhiyu-theme-static@1.0.9/img/Theme-AnZhiYu-2E67D3.svg" alt="本站使用AnZhiYu主题"></a></p></div><div id="footer-bar"><div class="footer-bar-links"><div class="footer-bar-left"><div id="footer-bar-tips"><div class="copyright">&copy;2020 - 2024 By <a class="footer-bar-link" href="/" title="InsectMk" target="_blank">InsectMk</a></div></div><div id="footer-type-tips"></div></div><div class="footer-bar-right"><a class="footer-bar-link" target="_blank" rel="noopener" href="https://github.com/anzhiyu-c/hexo-theme-anzhiyu" title="主题">主题</a><a class="footer-bar-link" target="_blank" rel="noopener" href="https://beian.miit.gov.cn/" title="蜀ICP备2023013851号-2">蜀ICP备2023013851号-2</a><a class="footer-bar-link" target="_blank" rel="noopener" href="https://beian.mps.gov.cn/#/query/webSearch?code=51142202000154" title="川公网安备51142202000154号">川公网安备51142202000154号</a></div></div></div></footer></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="sidebar-site-data site-data is-center"><a href="/archives/" title="archive"><div class="headline">文章</div><div class="length-num">121</div></a><a href="/tags/" title="tag"><div class="headline">标签</div><div class="length-num">117</div></a><a href="/categories/" title="category"><div class="headline">分类</div><div class="length-num">14</div></a></div><span class="sidebar-menu-item-title">功能</span><div class="sidebar-menu-item"><a class="darkmode_switchbutton menu-child" href="javascript:void(0);" title="显示模式"><i class="anzhiyufont anzhiyu-icon-circle-half-stroke"></i><span>显示模式</span></a></div><div class="back-menu-list-groups"><div class="back-menu-list-group"><div class="back-menu-list-title">网页</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://insectmk.cn/" title="主博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="主博客"><span class="back-menu-item-text">主博客</span></a><a class="back-menu-item" href="https://insectmk.top/" title="次博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="次博客"><span class="back-menu-item-text">次博客</span></a></div></div><div class="back-menu-list-group"><div class="back-menu-list-title">项目</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://gitee.com/insectmk/chatbot-web" title="智能聊天机器人网站"><img class="back-menu-item-icon" src="https://image.insectmk.cn/hexo-gitee-blog/project/icon/chatbot-web.jpg" alt="智能聊天机器人网站"><span class="back-menu-item-text">智能聊天机器人网站</span></a></div></div></div><div class="menus_items"><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-home"></use></svg><span>主页</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-hand-peace"></use></svg><span>娱乐</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/entertainment/gallery/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-images"></use></svg><span>图库</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-comments"></use></svg><span>交流</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/contact/comments/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-paper-plane"></use></svg><span>留言板</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/contact/link/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-link"></use></svg><span>友链</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-compass"></use></svg><span>目录</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/categories/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-archive"></use></svg><span>分类</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/tags/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-tags"></use></svg><span>标签</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/archives/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-folder-open"></use></svg><span>归档</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-server"></use></svg><span>服务</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/server/left4dead2/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-icons-left__dead_"></use></svg><span>求生之路</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/server/minecraft/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-minecraft"></use></svg><span>我的世界</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-clipboard"></use></svg><span>日志</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/log/website/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-website-with-different-sections"></use></svg><span>个人网站</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/log/pc/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-desktop"></use></svg><span>个人电脑</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-bars"></use></svg><span>其他</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/extend/remind/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-note"></use></svg><span>备忘</span></a></li></ul></div><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/about/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-id-card"></use></svg><span>关于</span></a></div></div><span class="sidebar-menu-item-title">标签</span><div class="card-tags"><div class="item-headline"></div><div class="card-tag-cloud"><a href="/tags/AOP/" style="font-size:.88rem">AOP<sup>1</sup></a><a href="/tags/Butterfly/" style="font-size:.88rem">Butterfly<sup>4</sup></a><a href="/tags/Docker/" style="font-size:.88rem">Docker<sup>6</sup></a><a href="/tags/ElementUI/" style="font-size:.88rem">ElementUI<sup>1</sup></a><a href="/tags/Frp/" style="font-size:.88rem">Frp<sup>1</sup></a><a href="/tags/Hexo/" style="font-size:.88rem;font-weight:500;color:var(--anzhiyu-lighttext)">Hexo<sup>8</sup></a><a href="/tags/IntelliJ-IDEA/" style="font-size:.88rem">IntelliJ IDEA<sup>1</sup></a><a href="/tags/JDK/" style="font-size:.88rem">JDK<sup>1</sup></a><a href="/tags/JWT/" style="font-size:.88rem">JWT<sup>1</sup></a><a href="/tags/Java/" style="font-size:.88rem">Java<sup>35</sup></a><a href="/tags/Junit/" style="font-size:.88rem">Junit<sup>1</sup></a><a href="/tags/Leanote/" style="font-size:.88rem">Leanote<sup>1</sup></a><a href="/tags/Maven/" style="font-size:.88rem">Maven<sup>2</sup></a><a href="/tags/MyBatisPlus/" style="font-size:.88rem">MyBatisPlus<sup>1</sup></a><a href="/tags/MySQL5-7/" style="font-size:.88rem">MySQL5.7<sup>1</sup></a><a href="/tags/Mybatis/" style="font-size:.88rem">Mybatis<sup>1</sup></a><a href="/tags/MybatisPlus/" style="font-size:.88rem">MybatisPlus<sup>1</sup></a><a href="/tags/OSS/" style="font-size:.88rem">OSS<sup>1</sup></a><a href="/tags/Spring/" style="font-size:.88rem">Spring<sup>2</sup></a><a href="/tags/Spring-Boot/" style="font-size:.88rem">SpringBoot<sup>6</sup></a><a href="/tags/Vue2/" style="font-size:.88rem">Vue2<sup>9</sup></a><a href="/tags/Vue3/" style="font-size:.88rem">Vue3<sup>1</sup></a><a href="/tags/Vuetify/" style="font-size:.88rem">Vuetify<sup>1</sup></a><a href="/tags/Vuex/" style="font-size:.88rem">Vuex<sup>1</sup></a><a href="/tags/Waline/" style="font-size:.88rem">Waline<sup>3</sup></a><a href="/tags/mvc/" style="font-size:.88rem">mvc<sup>3</sup></a><a href="/tags/mybatis/" style="font-size:.88rem">mybatis<sup>1</sup></a><a href="/tags/profile/" style="font-size:.88rem">profile<sup>1</sup></a><a href="/tags/spring/" style="font-size:.88rem">spring<sup>5</sup></a><a href="/tags/springboot/" style="font-size:.88rem">springboot<sup>4</sup></a><a href="/tags/transaction/" style="font-size:.88rem">transaction<sup>1</sup></a><a href="/tags/yaml/" style="font-size:.88rem">yaml<sup>2</sup></a><a href="/tags/%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/" style="font-size:.88rem">个人博客<sup>11</sup></a><a href="/tags/%E4%BA%8B%E5%8A%A1/" style="font-size:.88rem">事务<sup>1</sup></a><a href="/tags/%E5%88%86%E9%A1%B5/" style="font-size:.88rem">分页<sup>1</sup></a><a href="/tags/%E5%89%8D%E7%AB%AF/" style="font-size:.88rem;font-weight:500;color:var(--anzhiyu-lighttext)">前端<sup>1</sup></a><a href="/tags/%E6%9C%8D%E5%8A%A1%E5%99%A8/" style="font-size:.88rem">服务器<sup>20</sup></a><a href="/tags/%E6%AF%95%E4%B8%9A%E8%AE%BE%E8%AE%A1/" style="font-size:.88rem">毕业设计<sup>14</sup></a><a href="/tags/%E7%A6%85%E9%81%93/" style="font-size:.88rem">禅道<sup>1</sup></a><a href="/tags/%E7%BB%BF%E8%89%B2%E8%A7%A3%E5%8E%8B/" style="font-size:.88rem">绿色解压<sup>1</sup></a></div></div><hr></div></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="anzhiyufont anzhiyu-icon-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="anzhiyufont anzhiyu-icon-circle-half-stroke"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="anzhiyufont anzhiyu-icon-arrows-left-right"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="设置"><i class="anzhiyufont anzhiyu-icon-gear"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="anzhiyufont anzhiyu-icon-list-ul"></i></button><button id="chat-btn" type="button" title="聊天"><i class="anzhiyufont anzhiyu-icon-comment-sms"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="anzhiyufont anzhiyu-icon-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="anzhiyufont anzhiyu-icon-arrow-up"></i></button></div></div><div id="nav-music"><a id="nav-music-hoverTips" onclick="anzhiyu.musicToggle()" accesskey="m">播放音乐</a><div id="console-music-bg"></div><meting-js id="975968032" server="netease" type="playlist" mutex="true" preload="none" theme="var(--anzhiyu-main)" data-lrctype="0" order="random" volume="0.7"></meting-js></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="anzhiyufont anzhiyu-icon-xmark"></i></button></nav><div class="is-center" id="loading-database"><i class="anzhiyufont anzhiyu-icon-spinner anzhiyu-pulse-icon"></i><span> 数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"></div></div><hr><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div id="rightMenu"><div class="rightMenu-group rightMenu-small"><div class="rightMenu-item" id="menu-backward"><i class="anzhiyufont anzhiyu-icon-arrow-left"></i></div><div class="rightMenu-item" id="menu-forward"><i class="anzhiyufont anzhiyu-icon-arrow-right"></i></div><div class="rightMenu-item" id="menu-refresh"><i class="anzhiyufont anzhiyu-icon-arrow-rotate-right" style="font-size:1rem"></i></div><div class="rightMenu-item" id="menu-top"><i class="anzhiyufont anzhiyu-icon-arrow-up"></i></div></div><div class="rightMenu-group rightMenu-line rightMenuPlugin"><div class="rightMenu-item" id="menu-copytext"><i class="anzhiyufont anzhiyu-icon-copy"></i><span>复制选中文本</span></div><div class="rightMenu-item" id="menu-pastetext"><i class="anzhiyufont anzhiyu-icon-paste"></i><span>粘贴文本</span></div><a class="rightMenu-item" id="menu-commenttext"><i class="anzhiyufont anzhiyu-icon-comment-medical"></i><span>引用到评论</span></a><div class="rightMenu-item" id="menu-newwindow"><i class="anzhiyufont anzhiyu-icon-window-restore"></i><span>新窗口打开</span></div><div class="rightMenu-item" id="menu-copylink"><i class="anzhiyufont anzhiyu-icon-link"></i><span>复制链接地址</span></div><div class="rightMenu-item" id="menu-copyimg"><i class="anzhiyufont anzhiyu-icon-images"></i><span>复制此图片</span></div><div class="rightMenu-item" id="menu-downloadimg"><i class="anzhiyufont anzhiyu-icon-download"></i><span>下载此图片</span></div><div class="rightMenu-item" id="menu-newwindowimg"><i class="anzhiyufont anzhiyu-icon-window-restore"></i><span>新窗口打开图片</span></div><div class="rightMenu-item" id="menu-search"><i class="anzhiyufont anzhiyu-icon-magnifying-glass"></i><span>站内搜索</span></div><div class="rightMenu-item" id="menu-searchBaidu"><i class="anzhiyufont anzhiyu-icon-magnifying-glass"></i><span>百度搜索</span></div><div class="rightMenu-item" id="menu-music-toggle"><i class="anzhiyufont anzhiyu-icon-play"></i><span>播放音乐</span></div><div class="rightMenu-item" id="menu-music-back"><i class="anzhiyufont anzhiyu-icon-backward"></i><span>切换到上一首</span></div><div class="rightMenu-item" id="menu-music-forward"><i class="anzhiyufont anzhiyu-icon-forward"></i><span>切换到下一首</span></div><div class="rightMenu-item" id="menu-music-playlist" onclick="window.open(&quot;https://y.qq.com/n/ryqq/playlist/8802438608&quot;, &quot;_blank&quot;);" style="display:none"><i class="anzhiyufont anzhiyu-icon-radio"></i><span>查看所有歌曲</span></div><div class="rightMenu-item" id="menu-music-copyMusicName"><i class="anzhiyufont anzhiyu-icon-copy"></i><span>复制歌名</span></div></div><div class="rightMenu-group rightMenu-line rightMenuOther"><a class="rightMenu-item menu-link" id="menu-randomPost"><i class="anzhiyufont anzhiyu-icon-shuffle"></i><span>随便逛逛</span></a><a class="rightMenu-item menu-link" href="/categories/"><i class="anzhiyufont anzhiyu-icon-cube"></i><span>博客分类</span></a><a class="rightMenu-item menu-link" href="/tags/"><i class="anzhiyufont anzhiyu-icon-tags"></i><span>文章标签</span></a></div><div class="rightMenu-group rightMenu-line rightMenuOther"><a class="rightMenu-item" id="menu-copy" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-copy"></i><span>复制地址</span></a><a class="rightMenu-item" id="menu-commentBarrage" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-message"></i><span class="menu-commentBarrage-text">关闭热评</span></a><a class="rightMenu-item" id="menu-darkmode" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-circle-half-stroke"></i><span class="menu-darkmode-text">深色模式</span></a><a class="rightMenu-item" id="menu-translate" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-language"></i><span>轉為繁體</span></a></div></div><div id="rightmenu-mask"></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.cbd.int/@fancyapps/ui@5.0.28/dist/fancybox/fancybox.umd.js"></script><script src="https://cdn.cbd.int/instant.page@5.2.0/instantpage.js" type="module"></script><script src="https://cdn.cbd.int/node-snackbar@0.1.16/dist/snackbar.min.js"></script><canvas id="universe"></canvas><script async src="https://npm.elemecdn.com/anzhiyu-theme-static@1.0.0/dark/dark.js"></script><script>var HoldLog=console.log;console.log=function(){};let now1=new Date;queueMicrotask(()=>{function o(){HoldLog.apply(console,arguments)}var c=new Date("04/11/2022 14:03:44"),c=(now1.setTime(now1.getTime()+250),(now1-c)/1e3/60/60/24),c=["欢迎使用安知鱼!","生活明朗, 万物可爱",`
        
       █████╗ ███╗   ██╗███████╗██╗  ██╗██╗██╗   ██╗██╗   ██╗
      ██╔══██╗████╗  ██║╚══███╔╝██║  ██║██║╚██╗ ██╔╝██║   ██║
      ███████║██╔██╗ ██║  ███╔╝ ███████║██║ ╚████╔╝ ██║   ██║
      ██╔══██║██║╚██╗██║ ███╔╝  ██╔══██║██║  ╚██╔╝  ██║   ██║
      ██║  ██║██║ ╚████║███████╗██║  ██║██║   ██║   ╚██████╔╝
      ╚═╝  ╚═╝╚═╝  ╚═══╝╚══════╝╚═╝  ╚═╝╚═╝   ╚═╝    ╚═════╝
        
        `,"已上线",Math.floor(c),"天","©2020 By 安知鱼 V1.6.12"],e=["NCC2-036","调用前置摄像头拍照成功，识别为【小笨蛋】.","Photo captured: ","🤪"];setTimeout(o.bind(console,`
%c${c[0]} %c ${c[1]} %c ${c[2]} %c${c[3]}%c ${c[4]}%c ${c[5]}

%c ${c[6]}
`,"color:#425AEF","","color:#425AEF","color:#425AEF","","color:#425AEF","")),setTimeout(o.bind(console,`%c ${e[0]} %c ${e[1]} %c 
${e[2]} %c
${e[3]}
`,"color:white; background-color:#4fd953","","",'background:url("https://npm.elemecdn.com/anzhiyu-blog@1.1.6/img/post/common/tinggge.gif") no-repeat;font-size:450%')),setTimeout(o.bind(console,"%c WELCOME %c 你好，小笨蛋.","color:white; background-color:#4f90d9","")),setTimeout(console.warn.bind(console,"%c ⚡ Powered by 安知鱼 %c 你正在访问 InsectMk 的博客.","color:white; background-color:#f0ad4e","")),setTimeout(o.bind(console,"%c W23-12 %c 你已打开控制台.","color:white; background-color:#4f90d9","")),setTimeout(console.warn.bind(console,"%c S013-782 %c 你现在正处于监控中.","color:white; background-color:#d9534f",""))})</script><script async src="/anzhiyu/random.js"></script><script async>!function(){var n,r,o,a,i,e=new Date("04/11/2022 14:03:44"),l=new Date;setInterval(()=>{var t;if(l=new Date,i=l.getHours(),t=(l-e)/1e3/60/60/24,n=Math.floor(t),t=(l-e)/1e3/60/60-24*n,r=Math.floor(t),1==String(r).length&&(r="0"+r),t=(l-e)/1e3/60-1440*n-60*r,o=Math.floor(t),1==String(o).length&&(o="0"+o),t=(l-e)/1e3-86400*n-3600*r-60*o,a=Math.round(t),1==String(a).length&&(a="0"+a),document.getElementById("footer")){let e="";e=(i<18&&9<=i||null!=(t=document.querySelector("#workboard .workSituationImg"))&&(t.src="",t.title="",t.alt=""),`本站居然运行了 ${n} 天<span id='runtime'> ${r} 小时 ${o} 分 ${a} 秒 </span><i class='anzhiyufont anzhiyu-icon-heartbeat' style='color:red'></i>`),document.getElementById("runtimeTextTip")&&(document.getElementById("runtimeTextTip").innerHTML=e)}},1e3)}()</script><script src="/js/search/local-search.js"></script><div class="js-pjax"><script>(()=>{let e=()=>{Waline.init(Object.assign({el:"#waline-wrap",serverURL:"https://waline-server.insectmk.cn/",pageview:!0,dark:'html[data-theme="dark"]',path:window.location.pathname,comment:!0},{reaction:["/static/img/waline/tieba_agree.png","/static/img/waline/tieba_look_down.png","/static/img/waline/tieba_sunglasses.png","/static/img/waline/tieba_pick_nose.png","/static/img/waline/tieba_awkward.png","/static/img/waline/tieba_sleep.png"],requiredMeta:["nick","mail"],locale:{placeholder:"欢迎评论哟~"}}))};var i=async()=>{"object"==typeof Waline||(await getCSS("https://cdn.cbd.int/@waline/client@2.15.5/dist/waline.css"),await getScript("https://cdn.cbd.int/@waline/client@2.15.5/dist/waline.js")),e()};setTimeout(i,0)})()</script><input type="hidden" name="page-type" id="page-type" value="post"></div><script>window.addEventListener("load",()=>{let t=e=>e=""!==e&&150<(e=(e=(e=(e=e.replace(/<img.*?src="(.*?)"?[^\>]+>/gi,"[图片]")).replace(/<a[^>]+?href=["']?([^"']+)["']?[^>]*>([^<]+)<\/a>/gi,"[链接]")).replace(/<pre><code>.*?<\/pre>/gi,"[代码]")).replace(/<[^>]+>/g,"")).length?e.substring(0,150)+"...":e,a=t=>{let a="";if(t.length)for(let e=0;e<t.length;e++)a=(a=(a+="<div class='aside-list-item'>")+`<a href='${t[e].url}' class='thumbnail'><img src='${t[e].avatar}' alt='${t[e].nick}'></a>`)+`<div class='content'>
        <a class='comment' href='${t[e].url}' title='${t[e].content}'>${t[e].content}</a>
        <div class='name'><span>${t[e].nick} / </span><time datetime="${t[e].date}">${anzhiyu.diffDate(t[e].date,!0)}</time></div>
        </div></div>`;else a+="没有评论";var e=document.querySelector("#card-newest-comments .aside-list");e&&(e.innerHTML=a),window.lazyLoadInstance&&window.lazyLoadInstance.update(),window.pjax&&window.pjax.refresh(e)};var e=()=>{var e;document.querySelector("#card-newest-comments .aside-list")&&((e=saveToLocal.get("waline-newest-comments"))?a(JSON.parse(e)):(async()=>{try{var e=(await(await fetch("https://waline-server.insectmk.cn/api/comment?type=recent&count=6",{method:"GET"})).json()).data.map(e=>({content:t(e.comment),avatar:e.avatar,nick:e.nick,url:e.url+"#"+e.objectId,date:e.time||e.insertedAt}));saveToLocal.set("waline-newest-comments",JSON.stringify(e),10/1440),a(e)}catch(e){console.error(e),document.querySelector("#card-newest-comments .aside-list").textContent="无法获取评论，请确认相关配置是否正确"}})())};e(),document.addEventListener("pjax:complete",e)})</script><script>var visitorMail=""</script><script async data-pjax src="https://cdn.cbd.int/anzhiyu-theme-static@1.0.0/waterfall/waterfall.js"></script><script src="https://lf3-cdn-tos.bytecdntp.com/cdn/expire-1-M/qrcodejs/1.0.0/qrcode.min.js"></script><link rel="stylesheet" href="https://cdn.cbd.int/anzhiyu-theme-static@1.1.9/icon/ali_iconfont_css.css"><script async src="//at.alicdn.com/t/c/font_3795172_6hp27xdg2x7.js"></script><script>(()=>{var a,t,h,e;window.ChatraSetup={startHidden:!0},window.chatBtnFn=()=>{document.getElementById("chatra").classList.contains("chatra--expanded")?(Chatra("minimizeWidget"),Chatra("hide")):(Chatra("openChat",!0),Chatra("show"))};a=document,t=window,h="Chatra",t.ChatraID="SjkKhfiLMpdfaPPhc",e=a.createElement("script"),t[h]=t[h]||function(){(t[h].q=t[h].q||[]).push(arguments)},e.async=!0,e.src="https://call.chatra.io/chatra.js",a.head&&a.head.appendChild(e)})()</script><link rel="stylesheet" href="https://cdn.cbd.int/anzhiyu-theme-static@1.0.0/aplayer/APlayer.min.css" media="print" onload='this.media="all"'><script src="https://cdn.cbd.int/anzhiyu-blog-static@1.0.1/js/APlayer.min.js"></script><script src="https://cdn.cbd.int/hexo-anzhiyu-music@1.0.1/assets/js/Meting2.min.js"></script><script src="https://cdn.cbd.int/pjax@0.2.8/pjax.min.js"></script><script>let pjaxSelectors=["head > title","#config-diff","#body-wrap","#rightside-config-hide","#rightside-config-show",".js-pjax"];var pjax=new Pjax({elements:'a:not([target="_blank"])',selectors:pjaxSelectors,cacheBust:!1,analytics:!1,scrollRestoration:!1});document.addEventListener("pjax:send",function(){if(anzhiyu.removeGlobalFnEvent("pjax"),anzhiyu.removeGlobalFnEvent("themeChange"),document.getElementById("rightside").classList.remove("rightside-show"),window.aplayers)for(let e=0;e<window.aplayers.length;e++)window.aplayers[e].options.fixed||window.aplayers[e].destroy();"object"==typeof typed&&typed.destroy();var e=document.body.classList;e.contains("read-mode")&&e.remove("read-mode")}),document.addEventListener("pjax:complete",function(){window.refreshFn(),document.querySelectorAll("script[data-pjax]").forEach(e=>{let t=document.createElement("script");var a=e.text||e.textContent||e.innerHTML||"";Array.from(e.attributes).forEach(e=>t.setAttribute(e.name,e.value)),t.appendChild(document.createTextNode(a)),e.parentNode.replaceChild(t,e)}),GLOBAL_CONFIG.islazyload&&window.lazyLoadInstance.update(),"function"==typeof panguInit&&panguInit(),"function"==typeof gtag&&gtag("config","",{page_path:window.location.pathname}),"object"==typeof _hmt&&_hmt.push(["_trackPageview",window.location.pathname]),"function"==typeof loadMeting&&document.getElementsByClassName("aplayer").length&&loadMeting(),"object"==typeof Prism&&Prism.highlightAll()}),document.addEventListener("pjax:error",e=>{404===e.request.status&&pjax.loadUrl("/404")})</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><script charset="UTF-8" src="https://cdn.cbd.int/anzhiyu-theme-static@1.1.5/accesskey/accesskey.js"></script></div><div id="popup-window"><div class="popup-window-title">通知</div><div class="popup-window-divider"></div><div class="popup-window-content"><div class="popup-tip">你好呀</div><div class="popup-link"><i class="anzhiyufont anzhiyu-icon-arrow-circle-right"></i></div></div></div></body></html>